ST310 Course Project

The aim of this project is to demonstrate the use of machine learning techniques discussed in the ST310 Machine Learning module, in turn primarily drawing from (James, Gareth and Witten, Daniela and Hastie, Trevor and Robert Tibshirani 2017) and (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome 2009). We rely on both linear (Logistic Regression) and non-linear methods (Random Forests and Gradient Boosted Decision Trees) for a classification problem.

Remark: If executing this notebooks as a .Rmd file, ensure that all libraries and dependencies are installed and that the chunks are executed in sequential order.

Dataset

We have obtained data from the Kaggle March Tabular Playground competition. The data consists of anonymised features, which correspond to a binary outcome variable; in other words the task is a classification problem. Although the data is anonymised, the challenge description states:

The dataset used for this competition is synthetic but based on a real dataset and generated using a CTGAN. The original dataset deals with predicting the amount of an insurance claim. Although the features are anonymized, they have properties relating to real-world features.

We believe that this machine learning task is well-motivated as predicting the amount of an insurance claim, or whether an insurance claim occured, would be useful for helping an insurance company forecast its cash flow and manage risk.

The dataset consists of 30 features, 19 categorical variables and 11 numerical variables., and a binary outcome variable target. 73.5% of the observations have ‘target==1,’ suggesting an imbalanced dataset. We will need to process these categorical variables in some manner, which we shall consider in subsequent sections.

A challenge is that we have no specific domain knowledge about the meaning of particular features, and whether they may be useful. Nonetheless, we can resort to model interpretability methods (Molnar, Christoph 2019) to obtain an ex-post explanation of our models. In the linear case, we can examine coefficients and their statistical significance, and in the case of tree-based models, such as feature importances, partial dependence plots, and Shapley Values.

library(tidyverse)
library(ggplot2)
library(GGally)
library(patchwork)
library(broom)
library(tidymodels)
library(arm)
library(car) #outlier
library(tidyr)
library(glmnet)
library(caret)
library(randomForest)
library(xgboost)
library(catboost)
library(e1071)
library(data.table)
library(doParallel)
library(foreach)
library(pROC)
library(pdp)
df <- read.csv(file = "../data/train.csv")
cat(c("The dimensions of the array are :", dim(df)[1], ", ", dim(df)[2]))
The dimensions of the array are : 300000 ,  32

The dataset consists of 30 features, 19 categorical variables and 11 numerical variables., and a binary outcome variable target. We will need to process these categorical variables in some manner, which we shall consider in the subsequent section.

A challenge is that we have no specific domain knowledge about the meaning of particular features, and whether they may be useful. Nonetheless, we can resort to model interpretability methods (Molnar, Christoph 2019) to obtain an ex-post explanation of our models. In the linear case, we can examine coefficients and their statistical significance, and in the case of tree-based models, we can utilise feature importances, partial dependence plots, and Shapley Values.

Preprocessing

We remove the first column id, which represents an unique identifier for each observation. We then convert the first 19 columns, which are categorical variables into the factor data type in R, To reduce computational time, we subsample 4000 observations from the complete dataset of 300,000 observations. For our subsequent analysis, we will use only this subsample of 4000 observations, although the approaches can be extended to a larger dataset given greater computational resources. We further partition the 4000 observations, into a train set of 3000 observations and a test set of 1000 observations. All training and tuning are performed on the training data, and we will consider model performance on the test set performance scores.

Remark: Different models would require different preprocessing for the categorical variables, and thus we will further address in subsequent sections; for example the glm package can accept factors as a data type, whereas for glmnet they must be converted to the model.matrix format.

Remark: When encoding the categorical variables as dummy variables in our subsequent analysis, we find that there are over 600 unique categories across all 19 of the categorical variables. We could also consider different methods to process categorical variables, such as merging less frequently occuring categories, or target encoding (Parr, Terence and Howard, Jeremy 2019, ch. 6). Nonetheless, we stick with the factors and dummies approach given our lack of familiarity with these other methods.

cat_feats = 1:19 # the first 19 columns are categorical 
cont_feats <- 20:30 # and the next 11 are continuous
target_col <- 31 # target
# convert cats to factors
df <- column_to_rownames(df, var = "id") %>% 
         mutate_if(is.character,as.factor) %>% 
         mutate_at(vars(target), factor)
# subsample the data for faster model imputation
set.seed(1)
sam = sample(1:nrow(df), 4000)
df_sample = df[sam,]
# Partition data into train and test; test will be our oos data
set.seed(1)
df_split <- initial_split(df_sample, prop = 3/4)
df_train <- training(df_split)
df_test <- testing(df_split)

Exploratory Data Analysis

Univariate EDA

We observe that the univariate distributions of the continuous variables are all multi-modal and non-normal, but they are all normalised to the range of \([0, 1]\).

# flatten df into using pivot_longer and plot distribution
df %>% pivot_longer(cols = starts_with("cont"), names_to  = "cont") %>% 
   ggplot(aes(x = value))+
   geom_histogram(bins = 100, alpha = 0.85)+
   ggtitle("Continuous features distribution")+
   facet_wrap(cont~.,scales = "free") +
   theme_minimal()

From the distributions of categorical variables, we see that there are variables with substantially more observations in one category, and also variables with a high number of (\(>50\)) categories, which will be an issue to address in subsequent preprocessing.

# flatten df into using pivot_longer and plot distribution
df %>% pivot_longer(cols = contains(c("cat", "target")), names_to  = "cat") %>% 
   ggplot(aes(x = value))+
   geom_bar(alpha = 0.85)+
   ggtitle("Categorical features distribution")+
   facet_wrap(cat~.,scales = "free", ncol = 4) +
   theme_minimal(base_size = 30)

Bivariate EDA

We group the continuous variables by the target and plot them as boxplots to check for any obvious differences discernible by eye. From the plots, claims with target == 1 have lower values of cont3 on average (median) than claims with target == 0. Claims with target=1 also have a much higher median value of cont4 than claims with target == 0. Hence, we would expect cont3 and cont4 to have negative relationships with target. In addition, we see a group of observations at the tail ends for cont0, cont5, cont7, cont8, cont9, cont10, which may be indicative of outliers. This will be addressed at the end of this section.

# flatten df into using pivot_longer
# group by target and plot distribution
df[, c(cont_feats, target_col)] %>% 
  pivot_longer(cols = starts_with("cont"), names_to  = "var", values_to="value") %>% 
  ggplot(aes(x=target,y=value), fill=factor(value)) + 
  geom_boxplot() + coord_flip() + facet_wrap(~var, scales="free_x")

From our conditional boxplots, we can identify potential outliers. In particular we can spot many potential outliers for cont0, cont5, cont7, cont8, cont9 and cont10. We investigate the potential outliers spotted in the bivariate plots by identifying observations that lie at the extreme percentiles of those continuous variables. Using the Hampel filter, which considers points lying outside the median plus or minus 3 mean absolute deviations as outliers, more than 200 observations per variable were classified as such. This suggests that these may not be outliers but that the distribution is just heavy-tailed. Without further information on the reasonable scale of values that individual variables can take (along with the fact that they are all normalised), we find it challenging to identify outliers through descriptive statistics and decide not to exclude any such points using this approach. We will proceed to detect outliers in another approach in [section 3b].

hampel_filter <- function(df){
   lower_bound <- median(df) - 3 * mad(df, constant = 1)
   upper_bound <- median(df) + 3 * mad(df, constant = 1)
   outlier_ind <- which(df < lower_bound | df > upper_bound)
   return(outlier_ind)
}
percentile_filter <- function(df, lq = 0.001, uq = 0.999){
   lower_bound <- quantile(df, lq)
   upper_bound <- quantile(df, uq)
   outlier_ind <- which(df < lower_bound | df > upper_bound)
   return(outlier_ind)
}
hampel_count <- function(x){length(hampel_filter(x))}
pct_count <- function(x){length(percentile_filter(x))}

outlier_counts <- df_train[, cont_feats] %>% map_dfr(hampel_count)
outlier_counts[2, ] <- df_train[, cont_feats] %>% map_dfr(pct_count)
outlier_counts

For categorical variables, we use stacked bar plots to show the percentages of observations in each category that correspond to target == 0 and target == 1 respectively. A much larger proportion of claims with cat13 == B appear to be associated with target == 1 compared to cat13 == A. On the other hand, a much larger percentage of claims correspond to target == 0 if cat18 is A or B, than if cat18 is C or D.

# flatten df into using pivot_longer
# group by target and plot distribution
df[, c(cat_feats, target_col)] %>% 
  pivot_longer(cols = starts_with("cat"), names_to  = "cat", values_to="value") %>% 
  ggplot(aes(x = value, fill=target)) + 
    geom_bar(position="fill") + 
    scale_y_continuous(name = "Within group Percentage", labels = scales::percent) +
    facet_wrap(~cat, scales="free_x", ncol = 4) +
    theme_minimal(base_size = 40)

We also inspect the correlation matrix for our continuous variables. There seems to be a cluster of variables - cont1, cont2, cont8 - that are highly correlated with each other. This may be potentially indicative of multicollinearity, a concern when using linear models. In addition, we also consider the (Pearson) correlation and our continuous variables, although it is not necessarily meaningful in this case given our target is binary. However, we note that the continuous variables have Pearson correlations of roughly \([-0.2, 0.2]\), suggesting that there is some signal (in the form of information or an association) between the features and the target. We should note that the pearson correlation only describes a linear and pairwise association between the variables. As such there could be complex non-linear associations and interactions between the variables as well, which the presence of multi-modal distributions of the continuous featuers in our univariate EDA could suggest as well.

cor_matrix <- cor(df[, cont_feats])
heatmap(cor_matrix, main="Correlation Matrix (Clustered)")

cor_with_target <- rownames_to_column(data.frame(cor(df[, c(cont_feats)], as.numeric(df$target))))
names(cor_with_target) <- c("feature", "pearson_corr")
cor_with_target %>%
  ggplot(aes(x=reorder(feature, -pearson_corr), y = pearson_corr)) + 
  geom_bar(stat='identity') + coord_flip() + ggtitle("Pearson Correlation of Continuous with Target")

We can use Principal Components Analysis (PCA) as a means to visualise the data in low-dimension, to determine if there are any explicitly discernible trends. We apply PCA to all the continuous features, and no further pre-scaling is required given the continuous features have values from \([0, 1]\). By eye, there do not appear to be any significant difference in the PCA representations for each class, although there are many observations with target == 1 closer to the bottom of the ellipsoid formed by the first two PCA loadings. At least in the space formed by the first two princial components, the classes do not appear to be linearly separable, - which suggest a non-linear method may be more effective on this classification task. On examination of the explained variance ratio, plotting the variation in \(\mathbf{X}\) against the number of principal components, we find that the first two principal components only capture about \(\approx 60\%\) variation in the continuous variables. To capture \(\approx 90\%\) of the variation, we would need 6 of the continuous features, and for $% we would need 9. This could suggest that including more features could be beneficial, which would be a concern if we are to do feature selection.

pcs <- prcomp(df[,cont_feats])
set.seed(2021)
data.frame(pc1=pcs$x[,1], pc2=pcs$x[,2], target=df[, "target"]) %>%
ggplot(aes(x = pc1, y = pc2, colour = target)) + 
  geom_jitter(alpha=0.7) + ggtitle('Principal Components')

# cumulative variance
cumul_var <- cumsum(pcs$sdev^2 / sum(pcs$sdev^2))
ggplot(data.frame(feature = 1:11, cumul_var = cumul_var)) + 
  geom_line(aes(x = feature,y = cumul_var)) + ggtitle("Cumulative Explained Variance Ratio") +
  scale_y_continuous(labels=percent) + xlab("Number of Principal Components") + 
  ylab("Cumulative explained Variance Ratio")

Modelling

We first consider a naive model that always predicts a single label (in this case \(0\)) given it is the most frequently occurring class. In this case, the accuracy would \(1 - \hat{y} = 0.745\) This illustrates a potential issue with the accuracy metric - the naive accuracy is high due to the nature of the data, and hence subsequent model performances need to be compared with this benchmark.

We also consider the ROC-AUC metric (Receiving Operator Characteristic Area Under the Curve), and accuracy metric. Given the problem is one related to insurance, the modelling outcome of interest is not only to obtain the correct predictions (accuracy), but also accurate probabilities, which is what the AUC metric measures. The AUC metric calculates the area under the ROC-curve, the plot of the true positive rate or sensitivity \(\frac{TP}{TP + FN}\) against the false positive rate \(\frac{FN}{TN + FP}\), assessing the performance of the classifier’s predicted probabilities across all possible decision thresholds. A classifier that always predicts 0s would result in a baseline AUC of \(0.5\).

As we do not know the specific threshold relevant to the insurance context of the problem, we will report both accuracy, with a decision threshold set to \(> 0.5\), and the AUC score for all models considered. In practice, the decision threshold would largely depend on the objective of the modeller.

# train-test
X_train = as.matrix(df_train[, cont_feats])
y_train = as.numeric(as.matrix(df_train$target))
X_test = as.matrix(df_test[, cont_feats])
y_test = as.numeric(as.matrix(df_test$target))

diagnosis <- function(train_pred, test_pred, train_true, test_true){
  train_classes <- ifelse(train_pred > 0.5, 1,0)
  test_classes <- ifelse(test_pred > 0.5, 1,0)
  acc1 <- mean(train_classes == train_true)
  auc1 <- auc(roc(train_true, train_pred, quiet=TRUE))
  acc2 <- mean(test_classes == test_true)
  auc2 <- auc(roc(test_true, test_pred, quiet=TRUE))
  data.frame(train_acc=acc1, train_auc=auc1, test_acc = acc2, test_auc=auc2)
}


results = data.frame(diagnosis(rep(0, dim(df_train)[1]), 
                               rep(0, dim(df_test)[1]), 
                               df_train$target, df_test$target),
                     row.names=c("naive"))
results

Logistic Regression (SGD)

To fulfill the project requirements, we demonstrate a `from scratch’ Stochastic Gradient Descent routine for Logistic Regression. The derivation follows (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome 2009, 120–26)

Consider a matrix of variables \(X = (x_{1}, x_{2}, \ldots x_{n})^{T}\), where \(x_{i}\) denote the i-th row or observation, the target \(\mathbf{y} = (y_{1}, y_{2}, \ldots, y_{n})\). Let \(p(x_{i}; \beta) = exp(\beta^{T} x_{i})\)

We are interested in finding the coefficients \(\beta\), such that the logistic loss or negative log-likelihood is minimised. The logistic loss is given by:

\[ \begin{align}l(\boldsymbol{\beta}) &= -\sum_{i = 1}^{N} y_{i} log(p(x_{i} ; \boldsymbol{\beta})) + (1 - y_{i}) log(1 - p(x_{i} ; \boldsymbol{\beta}))\\ &= \sum_{i = 1}^{N} \left [ y_{i}log \left (\frac{p(x_{i} ; \boldsymbol{\beta})}{1 - p(x_{i} ; \boldsymbol{\beta})} \right) + log(1 - p(x_{i} ; \boldsymbol{\beta})) \right ]\\ l(\boldsymbol{\beta}) &= -\sum_{i = 1}^{N}\left [y_{i} \boldsymbol{\beta}^{T} x_{i} - log(1 + exp(x_{i}\boldsymbol{\beta})) \right ] \end{align} \]

With the inclusion of a regularisation term, in this case a \(L^{2}\) penalty, the loss function becomes:

\[ l(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} \left [y_{i} \boldsymbol{\beta}^{T} x_{i} - log(1 + exp(\boldsymbol{\beta}^{T}x_{i})) \right ] - \lambda \boldsymbol{\beta}^{T} \boldsymbol{\beta}\]

The gradient of the loss function with respect to the coefficients \(\mathbf{\beta}\) is given by:

\[\nabla(\boldsymbol{\beta}) = -\sum_{i = 1}^{N} \left [ y_{i} x_{i} - \frac{x_{i}exp(\boldsymbol{\beta}^{T} x_{i})}{1 + exp(\boldsymbol{\beta}^{T} x_{i})} \right] - \lambda 2\boldsymbol{\beta}\]

We apply stochastic gradient descent. In short, this relies on updating the coefficients \(\beta\) iteratively based on a step size \(\lambda\):

\(\beta_{t + 1} = \beta_{t} - \lambda \nabla(\boldsymbol{\beta}_{t})\)

We use the Barzilai-Borwein method (Murphy, Kevin P. 2012, 444–45) to determine the step size.

\(\lambda_{t} = \frac{|(\beta_{t} - \beta_{t - 1})^{T}(\nabla F(\beta_{t}) - \nabla F(\beta_{t - 1}))|}{\| \nabla F(\beta_{t}) - \nabla F(\beta_{t - 1}))\|^{2}}\)

# binary crossentropy / log-loss
log_loss <- function(x, y, betas, lambda){
  logits <- x %*% betas
  - (t(y) %*% logits - sum(log(1 + exp(logits))) + lambda * t(betas) %*% betas) / dim(x)[1]
}
# logistic regression gradients
gradients <- function(x, y, betas, lambda){
  logits <- x %*% betas
  - (t(x) %*% (y - exp(logits)/(1 + exp(logits)))) - lambda *2 * betas / dim(x)[1]
}
p = dim(X_train)[2]
lambda = 0
n_iters <- 100
init_step_size <- 1e-6
set.seed(2021)
beta_init <- matrix(rnorm(p),nrow=p)
beta_path <- matrix(rep(0, n_iters * p), nrow = n_iters, ncol=p)
beta_path[1,] = beta_init
last_grad <- grad <- gradients(X_train, y_train, beta_path[1,], lambda)
beta_path[2,] = beta_init - init_step_size * grad
grad <- gradients(X_train, y_train, beta_path[2,], lambda)
losses <- rep(0, n_iters)
for (i in 3:n_iters){
    step_size <- as.numeric(t(beta_path[i - 1,] - beta_path[i - 2,]) %*% (grad - last_grad) / 
                    (t(grad - last_grad) %*% (grad - last_grad)))
    beta_path[i,] <- beta_path[i - 1,] - step_size * grad
    last_grad <- grad
    grad <- gradients(X_train, y_train, beta_path[i, ], lambda)
    losses[i] <- log_loss(X_train, y_train, beta_path[i,], lambda)
}
ggplot(data.frame(step = 3:n_iters, loss=losses[3:n_iters])) + 
  geom_line(aes(x = step, y = loss)) +
  ggtitle("Binary Crossentropy vs. Iterations")


pred_train <- as.numeric(1 / (1 + exp(-X_train %*% beta_path[100,])))
pred_test <- as.numeric(1 / (1 + exp(-X_test %*% beta_path[100,])))
results["sgd",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["sgd",]

We apply our “from scratch” implementaton of SGD Logistic Regression using all the numerical variables, obtaining a test accuracy of \(0.751\) and a test AUC of \(0.7082\). Given the limitations of our implementation, for example an inability to process the factor datatype (unless we append a one-hot encoded matrix), we shall subsequently use the glm package for logistic regression, and the glmnet package for regularised logistic regression.

Logistic Regression (Few Predictors)

Having introduced logistic regression in the previous model, we seek to build a simpler model with better interpretability to compare the performance of all other models to. In this section, we build a logistic regression model with a few predictors, which are selected from our exploratory data analysis to have discernible differences in target. These are cont3, cont4, cat13, cat18. We will refer to this model as our baseline model.

glm1 <- glm(target~cont3+cont4+cat13+cat18,data=df_train, family=binomial(link="logit"))
summary(glm1)

Call:
glm(formula = target ~ cont3 + cont4 + cat13 + cat18, family = binomial(link = "logit"), 
    data = df_train)

Deviance Residuals: 
    Min       1Q   Median       3Q      Max  
-1.5707  -0.6702  -0.6021   0.3931   2.0095  

Coefficients:
            Estimate Std. Error z value Pr(>|z|)    
(Intercept)  -1.4821     1.0756  -1.378  0.16824    
cont3        -0.6554     0.2276  -2.880  0.00398 ** 
cont4        -0.4772     0.2063  -2.313  0.02070 *  
cat13B        1.8681     0.3346   5.584 2.36e-08 ***
cat18B        0.5581     1.0714   0.521  0.60243    
cat18C        2.6081     1.0816   2.411  0.01590 *  
cat18D        2.4342     1.0805   2.253  0.02427 *  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 3406.6  on 2999  degrees of freedom
Residual deviance: 2962.8  on 2993  degrees of freedom
AIC: 2976.8

Number of Fisher Scoring iterations: 4
vif(glm1)
          GVIF Df GVIF^(1/(2*Df))
cont3 1.110907  1        1.053996
cont4 1.053938  1        1.026615
cat13 1.010521  1        1.005247
cat18 1.066127  3        1.010729
ggcoef(glm1)

The generalised variance inflation factor (GVIF) tells us the extent to which the standard error of a predictor is increased due to its correlation with other predictors in the model, corrected by the number of degrees of freedom corresponding to the number of levels in the categorical variables. The GVIF of all predictors in our model are less than 2, which shows no evidence of multicollinearity. All four predictors are significant at 5% level, with the most significant predictor being cat13, which has a p-value of less than 1%. The coefficients of the predictors represent the association of that predictor with the log odds of target, which is defined as \[log P(target=1)/P(target=0)\]

The coefficients of the dummy variables indicate the average difference between the log odds of that factor level group compared to the baseline level group. In our regression, the first category (A) of each categorical variable is taken as the baseline group. For example, the coefficient of ‘cat13B’ implies the following equation: \[\log\frac{P(target=1|cat13=B)}{P(target=0|cat13=B)}-\log\frac{P(target=1|cat13=A)}{P(target=0|cat13=A)}=1.8681\] This means that claims with ‘cat13=B’ have exp(1.8681)-1=5.48 higher odds than claims with ‘cat13=A.’ The coefficient of cat18B is not significant, which implies that its association with target is not significantly different from ‘cat18=A.’ However, having ‘cat18=C’ makes the claim exp(2.6081)-1=12.6 times more likely to have ‘target==1’ than having ‘cat18=A.’ Similarly, claims with ‘cat18=D’ are exp(2.4342)-1=9.4 times more likely to have ‘target==1’ than claims with ‘cat18=A.’

To interpret the coefficients of the continuous variables, log odds need to be calculated using specific pairs of values of the predictors. The non-linearity of the logistic function means that a change of one unit in the value of a predictor is not the same across the range of the predictor. ‘cont3’ and ‘cont4’ have negative coefficients as expected, and are interpreted as follows. A one unit increase in ‘cont3’ is associated with an exp(-0.6554)=0.519 multiplicative effect on the odds, i.e. a 48% decrease in odds compared to the previous odds. Similarly, a claim with a one unit higher value of ‘cont4’ is 1-exp(-0.4772)=37.9% less likely to have ‘target==1’ than a claim with a one unit lower value of ‘cont4.’ We note that as all continuous variables in this dataset are normalised, increasing a variable by one unit implies increasing it by one standard deviation higher than the mean in its original units.

pred_train <- predict(glm1, df_train, type="response")
pred_test <- predict(glm1, df_test, type="response")
results["glm-small",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-small",]

Logistic Regression (All Predictors)

We now run a logistic regression using all 31 predictors (full model). The regression coefficients can be interpreted in a similar way as the baseline model. The regression output shows that all predictors are significant at 5%, but this is unreliable since the categorical variables have many levels (623 in total).

The full model has a higher train accuracy (0.801) but lower test accuracy (0.59) than the baseline model, which implies overfitting. The test AUC is 0.543, which is much lower than the baseline. This is an example of the bias-variance trade-off; the more complex, full model with 31 predictors has a lower bias but higher variance than the simpler, baseline model with 4 predictors. We also obtain an error: “prediction from a rank-deficient fit may be misleading” which suggests multicollinearity. In subsequent sections, we aim to overcome this to improve the stability of our model using shrinkage in [section 3b].

glm2 <- glm(target~., data=df_train, family=binomial(link="logit"), 
            control = list(maxit = 100))
# display(glm2)

pred_train <- predict(glm2, df_train, type="response")
glm2$xlevels = lapply(df[,cat_feats], levels)
pred_test <- predict(glm2, df_test, type="response")
results["glm-full",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-full",]
# anova(glm1, glm2, test="Chisq")

Outlier Detection

At this stage, we suspect that some outliers might be heavily influencing the performance of our models, and hence we seek to detect outliers using a few measures. Formally, outliers are defined as observations with a response vector that is unusual conditional on covariates (predictors). Firstly, we look for points with large (studentised) residuals and we can test if these residuals are significantly larger than those of other points by looking at the Bonferroni-adjusted p-values. 10 points are identified to have large studentised residuals with adjust p-values less than 0.05. We store the indices of these points to be removed later.

outlierTest(glm2)
outliers <- as.numeric(names(outlierTest(glm2)$p))

Observations that are far from the average covariate pattern are considered to have high leverage and can be measured using hat values. Here, there are at least 100 points with high leverage.

Finally, we measure for influence, which is an observation that is an outlier and have high leverage. These are likely to influence the regression coefficients and influence can be thought of as the product of leverage and outlier. Here, we plot studentised residuals against hat-values with the size of a circle being proportional to the Cook’s distance of an observation- a measure of influence.

influenceIndexPlot(glm2, vars = "hat")

influencePlot(glm2)

We observe that there are 4 observations with high influence. We remove these observations along with the points identified as outliers earlier (14 in total), and compare the performance of our updated model with the original model.

influencers <- as.numeric(rownames(influencePlot(glm2)))

glm2_influencers <- update(glm2, subset = c(-influencers))
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred
glm2_outliers <- update(glm2, subset = c(-outliers))
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred
removal_list <- union(outliers, influencers)
glm2_removed <- update(glm2, subset = c(-removal_list))
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred
compareCoefs(glm2, glm2_influencers, glm2_outliers, glm2_removed)
Calls:
1: glm(formula = target ~ ., family = binomial(link = "logit"), data = df_train, control 
  = list(maxit = 100))
2: glm(formula = target ~ ., family = binomial(link = "logit"), data = df_train, subset =
   c(-influencers), control = list(maxit = 100))
3: glm(formula = target ~ ., family = binomial(link = "logit"), data = df_train, subset =
   c(-outliers), control = list(maxit = 100))
4: glm(formula = target ~ ., family = binomial(link = "logit"), data = df_train, subset =
   c(-removal_list), control = list(maxit = 100))

              Model 1   Model 2   Model 3   Model 4
(Intercept) -8.16e+15 -8.16e+15 -8.16e+15 -8.16e+15
SE           1.38e+08  1.38e+08  1.38e+08  1.38e+08
                                                   
cat0B       -3.78e+14 -3.78e+14 -3.78e+14 -3.78e+14
SE           3.75e+06  3.75e+06  3.75e+06  3.75e+06
                                                   
cat1B       -2.28e+14 -2.28e+14 -2.28e+14 -2.28e+14
SE           1.28e+07  1.28e+07  1.28e+07  1.28e+07
                                                   
cat1C       -1.58e+14 -1.58e+14 -1.58e+14 -1.58e+14
SE           1.80e+07  1.80e+07  1.80e+07  1.80e+07
                                                   
cat1D       -4.65e+15 -4.65e+15 -4.65e+15 -4.65e+15
SE           5.11e+07  5.11e+07  5.11e+07  5.11e+07
                                                   
cat1E       -3.40e+14 -3.40e+14 -3.40e+14 -3.40e+14
SE           4.35e+07  4.35e+07  4.35e+07  4.35e+07
                                                   
cat1F       -7.06e+13 -7.06e+13 -7.06e+13 -7.06e+13
SE           8.67e+06  8.67e+06  8.67e+06  8.67e+06
                                                   
cat1G        4.47e+13  4.47e+13  4.47e+13  4.47e+13
SE           1.11e+07  1.11e+07  1.11e+07  1.11e+07
                                                   
cat1H       -9.18e+13 -9.18e+13 -9.18e+13 -9.18e+13
SE           1.00e+07  1.00e+07  1.00e+07  1.00e+07
                                                   
cat1I       -2.10e+14 -2.10e+14 -2.10e+14 -2.10e+14
SE           8.17e+06  8.17e+06  8.17e+06  8.17e+06
                                                   
cat1J       -5.08e+14 -5.08e+14 -5.08e+14 -5.08e+14
SE           1.08e+07  1.08e+07  1.08e+07  1.08e+07
                                                   
cat1K        9.05e+13  9.05e+13  9.05e+13  9.05e+13
SE           8.94e+06  8.94e+06  8.94e+06  8.94e+06
                                                   
cat1L        7.08e+13  7.08e+13  7.08e+13  7.08e+13
SE           9.38e+06  9.38e+06  9.38e+06  9.38e+06
                                                   
cat1M       -1.25e+14 -1.25e+14 -1.25e+14 -1.25e+14
SE           1.05e+07  1.05e+07  1.05e+07  1.05e+07
                                                   
cat1N        7.56e+13  7.56e+13  7.56e+13  7.56e+13
SE           1.01e+07  1.01e+07  1.01e+07  1.01e+07
                                                   
cat1O        1.80e+14  1.80e+14  1.80e+14  1.80e+14
SE           1.23e+07  1.23e+07  1.23e+07  1.23e+07
                                                   
cat2B       -4.08e+14 -4.08e+14 -4.08e+14 -4.08e+14
SE           4.94e+07  4.94e+07  4.94e+07  4.94e+07
                                                   
cat2C       -2.02e+14 -2.02e+14 -2.02e+14 -2.02e+14
SE           4.92e+06  4.92e+06  4.92e+06  4.92e+06
                                                   
cat2D        3.58e+14  3.58e+14  3.58e+14  3.58e+14
SE           5.67e+06  5.67e+06  5.67e+06  5.67e+06
                                                   
cat2F       -1.10e+14 -1.10e+14 -1.10e+14 -1.10e+14
SE           8.23e+06  8.23e+06  8.23e+06  8.23e+06
                                                   
cat2G        1.14e+14  1.14e+14  1.14e+14  1.14e+14
SE           5.98e+06  5.98e+06  5.98e+06  5.98e+06
                                                   
cat2H       -3.66e+14 -3.66e+14 -3.66e+14 -3.66e+14
SE           4.56e+07  4.56e+07  4.56e+07  4.56e+07
                                                   
cat2I        2.63e+13  2.63e+13  2.63e+13  2.63e+13
SE           1.09e+07  1.09e+07  1.09e+07  1.09e+07
                                                   
cat2J       -2.25e+14 -2.25e+14 -2.25e+14 -2.25e+14
SE           8.88e+06  8.88e+06  8.88e+06  8.88e+06
                                                   
cat2L        1.46e+14  1.46e+14  1.46e+14  1.46e+14
SE           1.16e+07  1.16e+07  1.16e+07  1.16e+07
                                                   
cat2M       -4.23e+14 -4.23e+14 -4.23e+14 -4.23e+14
SE           1.03e+07  1.03e+07  1.03e+07  1.03e+07
                                                   
cat2N       -5.64e+14 -5.64e+14 -5.64e+14 -5.64e+14
SE           4.17e+07  4.17e+07  4.17e+07  4.17e+07
                                                   
cat2O        6.78e+14  6.78e+14  6.78e+14  6.78e+14
SE           1.55e+07  1.55e+07  1.55e+07  1.55e+07
                                                   
cat2Q       -1.16e+14 -1.16e+14 -1.16e+14 -1.16e+14
SE           8.96e+06  8.96e+06  8.96e+06  8.96e+06
                                                   
cat2S       -6.09e+15 -6.09e+15 -6.09e+15 -6.09e+15
SE           7.04e+07  7.04e+07  7.04e+07  7.04e+07
                                                   
cat2U       -1.58e+15 -1.58e+15 -1.58e+15 -1.58e+15
SE           4.63e+07  4.63e+07  4.63e+07  4.63e+07
                                                   
cat3B       -3.86e+12 -3.86e+12 -3.86e+12 -3.86e+12
SE           3.43e+06  3.43e+06  3.43e+06  3.43e+06
                                                   
cat3C        8.28e+13  8.28e+13  8.28e+13  8.28e+13
SE           6.66e+06  6.66e+06  6.66e+06  6.66e+06
                                                   
cat3D        1.36e+14  1.36e+14  1.36e+14  1.36e+14
SE           8.81e+06  8.81e+06  8.81e+06  8.81e+06
                                                   
cat3E        2.28e+14  2.28e+14  2.28e+14  2.28e+14
SE           1.52e+07  1.52e+07  1.52e+07  1.52e+07
                                                   
cat3F        2.80e+13  2.80e+13  2.80e+13  2.80e+13
SE           1.71e+07  1.71e+07  1.71e+07  1.71e+07
                                                   
cat3G       -1.81e+15 -1.81e+15 -1.81e+15 -1.81e+15
SE           3.16e+07  3.16e+07  3.16e+07  3.16e+07
                                                   
cat3H       -3.54e+15 -3.54e+15 -3.54e+15 -3.54e+15
SE           4.11e+07  4.11e+07  4.11e+07  4.11e+07
                                                   
cat3I       -3.23e+14 -3.23e+14 -3.23e+14 -3.23e+14
SE           3.39e+07  3.39e+07  3.39e+07  3.39e+07
                                                   
cat3J       -2.93e+15 -2.93e+15 -2.93e+15 -2.93e+15
SE           3.61e+07  3.61e+07  3.61e+07  3.61e+07
                                                   
cat3K       -2.66e+14 -2.66e+14 -2.66e+14 -2.66e+14
SE           2.72e+07  2.72e+07  2.72e+07  2.72e+07
                                                   
cat3L        1.86e+15  1.86e+15  1.86e+15  1.86e+15
SE           4.56e+07  4.56e+07  4.56e+07  4.56e+07
                                                   
cat3N       -1.39e+15 -1.39e+15 -1.39e+15 -1.39e+15
SE           4.25e+07  4.25e+07  4.25e+07  4.25e+07
                                                   
cat4B        4.58e+15  4.58e+15  4.58e+15  4.58e+15
SE           1.07e+08  1.07e+08  1.07e+08  1.07e+08
                                                   
cat4C        5.65e+15  5.65e+15  5.65e+15  5.65e+15
SE           1.05e+08  1.05e+08  1.05e+08  1.05e+08
                                                   
cat4D         4.2e+15   4.2e+15   4.2e+15   4.2e+15
SE            1.0e+08   1.0e+08   1.0e+08   1.0e+08
                                                   
cat4E        4.34e+15  4.34e+15  4.34e+15  4.34e+15
SE           1.00e+08  1.00e+08  1.00e+08  1.00e+08
                                                   
cat4F        4.46e+15  4.46e+15  4.46e+15  4.46e+15
SE           1.00e+08  1.00e+08  1.00e+08  1.00e+08
                                                   
cat4G        4.32e+15  4.32e+15  4.32e+15  4.32e+15
SE           1.00e+08  1.00e+08  1.00e+08  1.00e+08
                                                   
cat4H        4.17e+15  4.17e+15  4.17e+15  4.17e+15
SE           1.01e+08  1.01e+08  1.01e+08  1.01e+08
                                                   
cat4I        3.74e+15  3.74e+15  3.74e+15  3.74e+15
SE           1.02e+08  1.02e+08  1.02e+08  1.02e+08
                                                   
cat4J        4.37e+15  4.37e+15  4.37e+15  4.37e+15
SE           1.01e+08  1.01e+08  1.01e+08  1.01e+08
                                                   
cat4K        4.00e+15  4.00e+15  4.00e+15  4.00e+15
SE           1.02e+08  1.02e+08  1.02e+08  1.02e+08
                                                   
cat4L        3.53e+15  3.53e+15  3.53e+15  3.53e+15
SE           1.14e+08  1.14e+08  1.14e+08  1.14e+08
                                                   
cat4M        5.91e+15  5.91e+15  5.91e+15  5.91e+15
SE           1.05e+08  1.05e+08  1.05e+08  1.05e+08
                                                   
cat4N       -8.31e+14 -8.31e+14 -8.31e+14 -8.31e+14
SE           1.22e+08  1.22e+08  1.22e+08  1.22e+08
                                                   
cat4O        5.04e+15  5.04e+15  5.04e+15  5.04e+15
SE           1.09e+08  1.09e+08  1.09e+08  1.09e+08
                                                   
cat4S        4.61e+15  4.61e+15  4.61e+15  4.61e+15
SE           1.12e+08  1.12e+08  1.12e+08  1.12e+08
                                                   
cat4T        5.82e+14  5.82e+14  5.82e+14  5.82e+14
SE           1.12e+08  1.12e+08  1.12e+08  1.12e+08
                                                   
cat5AB       4.52e+15  4.52e+15  4.52e+15  4.52e+15
SE           1.12e+08  1.12e+08  1.12e+08  1.12e+08
                                                   
cat5AE       6.74e+14  6.74e+14  6.74e+14  6.74e+14
SE           1.22e+08  1.22e+08  1.22e+08  1.22e+08
                                                   
cat5AF       2.17e+15  2.17e+15  2.17e+15  2.17e+15
SE           1.32e+08  1.32e+08  1.32e+08  1.32e+08
                                                   
cat5AK      -2.22e+14 -2.22e+14 -2.22e+14 -2.22e+14
SE           1.13e+08  1.13e+08  1.13e+08  1.13e+08
                                                   
cat5AL       4.64e+15  4.64e+15  4.64e+15  4.64e+15
SE           1.16e+08  1.16e+08  1.16e+08  1.16e+08
                                                   
cat5AM       7.76e+15  7.76e+15  7.76e+15  7.76e+15
SE           1.52e+08  1.52e+08  1.52e+08  1.52e+08
                                                   
cat5AO       8.03e+14  8.03e+14  8.03e+14  8.03e+14
SE           1.12e+08  1.12e+08  1.12e+08  1.12e+08
                                                   
cat5AP       1.08e+15  1.08e+15  1.08e+15  1.08e+15
SE           1.06e+08  1.06e+08  1.06e+08  1.06e+08
                                                   
cat5AQ       4.69e+15  4.69e+15  4.69e+15  4.69e+15
SE           1.32e+08  1.32e+08  1.32e+08  1.32e+08
                                                   
cat5AR       3.91e+15  3.91e+15  3.91e+15  3.91e+15
SE           1.24e+08  1.24e+08  1.24e+08  1.24e+08
                                                   
cat5AS       2.61e+15  2.61e+15  2.61e+15  2.61e+15
SE           1.23e+08  1.23e+08  1.23e+08  1.23e+08
                                                   
cat5AT       1.08e+16  1.08e+16  1.08e+16  1.08e+16
SE           1.43e+08  1.43e+08  1.43e+08  1.43e+08
                                                   
cat5AU       3.01e+15  3.01e+15  3.01e+15  3.01e+15
SE           1.31e+08  1.31e+08  1.31e+08  1.31e+08
                                                   
cat5AV       1.56e+15  1.56e+15  1.56e+15  1.56e+15
SE           1.22e+08  1.22e+08  1.22e+08  1.22e+08
                                                   
cat5AW       3.09e+15  3.09e+15  3.09e+15  3.09e+15
SE           1.19e+08  1.19e+08  1.19e+08  1.19e+08
                                                   
cat5AX       8.56e+14  8.56e+14  8.56e+14  8.56e+14
SE           1.17e+08  1.17e+08  1.17e+08  1.17e+08
                                                   
cat5AY       1.17e+15  1.17e+15  1.17e+15  1.17e+15
SE           1.22e+08  1.22e+08  1.22e+08  1.22e+08
                                                   
cat5BA       3.80e+15  3.80e+15  3.80e+15  3.80e+15
SE           1.19e+08  1.19e+08  1.19e+08  1.19e+08
                                                   
cat5BB       3.67e+15  3.67e+15  3.67e+15  3.67e+15
SE           1.23e+08  1.23e+08  1.23e+08  1.23e+08
                                                   
cat5BC       5.99e+15  5.99e+15  5.99e+15  5.99e+15
SE           1.38e+08  1.38e+08  1.38e+08  1.38e+08
                                                   
cat5BE       1.68e+15  1.68e+15  1.68e+15  1.68e+15
SE           1.19e+08  1.19e+08  1.19e+08  1.19e+08
                                                   
cat5BF      -5.25e+15 -5.25e+15 -5.25e+15 -5.25e+15
SE           1.47e+08  1.47e+08  1.47e+08  1.47e+08
                                                   
cat5BG        1.4e+14   1.4e+14   1.4e+14   1.4e+14
SE            1.2e+08   1.2e+08   1.2e+08   1.2e+08
                                                   
cat5BH       8.97e+15  8.97e+15  8.97e+15  8.97e+15
SE           1.34e+08  1.34e+08  1.34e+08  1.34e+08
                                                   
cat5BI       4.81e+15  4.81e+15  4.81e+15  4.81e+15
 [ reached getOption("max.print") -- omitted 1124 rows ]
# actually just use glm2 and glm2_removed

Removing outliers led to a higher test accuracy of 0.684 but a lower test AUC of 0.539. We cannot interpret this further without knowing the specific threshold used to classify the target in the data. Analysing the regression output, we see that leaving out the outliers does not change the coefficient estimates, and since we have no intuitive reason to believe that these outlier values are extreme (due to no knowledge about the variables themselves), we decided to keep these outlier data points for all other models.

Regularised Logistic Regression

Given the issue of high dimensionality, we consider a regularised form of logistic regression. Specifically, we consider ridge (logistic) regression. This method shrinks coefficients by imposing a penalty on their size, thereby reducing model complexity. We use the implementation offered by the glmnet package; in doing so we need to convert the data type into matrices.The glmnet package requires the data to be in a matrix data type, and hence we make the corresponding adjustment.

X_train = df_train[, -length(df_train)]
y_train <- df_train$target
X_test = df_test[, -length(df_test)]
y_test <- df_test$target
X_train = model.matrix(~., X_train)
X_test = model.matrix(~., X_test)
glm3 <- cv.glmnet(X_train, y_train, 
                  family="binomial"(link="logit"), alpha=0)
glm3

Call:  cv.glmnet(x = X_train, y = y_train, family = binomial(link = "logit"),      alpha = 0) 

Measure: GLM Deviance 

    Lambda Index Measure      SE Nonzero
min 0.1561    79  0.7903 0.01767     458
1se 0.3957    69  0.8079 0.01554     458
pred_train <- as.numeric(predict(glm3, X_train, type="response"))
pred_test <- as.numeric(predict(glm3, X_test, type="response"))
results["glm-ridge",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["glm-ridge",]

Random Forest

To improve performance, we draw on the usage of non-linear tree-based models, specifically random forests. Intuitively, a random forest averages different decision trees (known as bagging) so as to reduce the variance of individual trees.

rf_recipe <- recipe(target~., data = df_train)

rf_model <- 
  rand_forest(trees=100) %>%
  set_engine("ranger", importance="impurity", seed=2021) %>%
  set_mode("classification")

rf_workflow <- workflow() %>%
  add_recipe(rf_recipe) %>%
  add_model(rf_model)

rf1 <- fit(rf_workflow, df_train)
ranger_obj <- pull_workflow_fit(rf1)$fit
# plot feature importances
rf_feat_imp <- rownames_to_column(data.frame(ranger_obj$variable.importance));
names(rf_feat_imp) <- c("feat", "importance")
ggplot(rf_feat_imp, aes(x = reorder(feat, importance), y = importance))+ 
      geom_bar(stat="identity", position="dodge")+ coord_flip()+
      ylab("Feature Importance (Gini Impurity)")+
      xlab("Feature")+
      ggtitle("Random Forest Feature Importances")
#evaluate metrics
pred_train <- unlist(predict(rf1,df_train,type='prob')[,2])
pred_test <- unlist(predict(rf1, df_test, type='prob')[,2])
results["rf",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["rf",]
temp <- function(x){partial(ranger_obj, train=df_train, pred.var = x, plot = TRUE, plot.engine = "ggplot2", paropts = list(.packages = "ranger"))}
plots <- lapply(names(df_train)[cont_feats], temp)

The random forest has a test accuracy of 0.836 and a test AUC of 0.872, which is higher than the previous linear models. However, the train accuracy and AUC are significantly higher than the test performance, which suggest that there may be some degree of overfitting to the train data.

Random forests can be used to rank the importance of different features. Specifically, the x-axis is the Mean Decrease Accuracy, which reports how much accuracy the model loses when we exclude this variable. The more the accuracy falls by, the more important the particular variable is. Note here that for categorical variables, each level of the category is classified as a single variable. In this plot, we recorded the 30 most important variables.

We then run another random forest with the most important features. In doing so, we hope to reduce the degree of overfitting by reducing the complexity of the model. However, it does not make sense to drop some levels of a categorical variable while including the other levels. Hence, as long as a level is present in the top 30 features, we will include the entire category in our updated random forest model. This results in us keeping only 22 variables, from an initial 30.

Our reduced random forest has a slightly improved test accuracy and a slightly decreased test AUC. However, it does not solve the potential problem of overfitting as train performance is still significantly better than test performance. In fact, train performance on the reduced random forest is better than the random forest with a full set of variables - the reduced complexity of the model enabled it to have a lower bias on the training set.

XGBoost

For completeness, we also consider the xgboost library for gradient boosted decision trees. Gradient Boosted Decision Trees. The XGBoost package, introduced in (Chen, Tianqi and Guestrin, Carlos 2016) is a variant of Gradient Boosted Decision Trees (Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome 2009, 353–74). For Gradient Boosting Trees, each decision tree is trained sequentially on the residuals of the previous decision tree, which has the effect of reducing bias.

dmy_train <- dummyVars("~.", data = df_train[,-length(df_train)])
dmy_test <- dummyVars("~.", data = df_test[,-length(df_test)])
X_train <- as.matrix(data.frame(predict(dmy_train,df_train)))
X_test <- as.matrix(data.frame(predict(dmy_test,df_test)))
y_train = as.integer(as.matrix(df_train$target))
y_test = as.integer(as.matrix(df_test$target))
bst <- xgboost(data = X_train, label=y_train, max_depth = 2, nround = 10, 
               verbose=0,
               objective='binary:logistic',
               eval_metric="logloss")

pred_train <- predict(bst, X_train, type="response")
pred_test <- predict(bst, X_test, type="response")
results["xgb",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["xgb",]

importance_matrix <- xgb.importance(model=bst)
xgb.plot.importance(importance_matrix)

# shapley values  
xgboost::xgb.ggplot.shap.summary(X_test, model = bst, 
                                 target_class = 1, top_n = 20)  # Summary plot

CatBoost

We also consider briefly examine the catboost library for gradient boosted decision trees, given its popularity on machine learning competitions such as Kaggle. The CatBoost library has the advantage of learning a target encoding, i.e. some numerical value for every category for each categorical variables. From an implementation point of view, this may reduce the preprocessing that may be required.For details on CatBoost, refer to (Prokhorenkova, Liudmila and Gusev, Gleb and Vorobev, Aleksandr and Dorogush, Anna Veronika and Gulin, Andrey 2017).

X_train = df_train[,c(cat_feats, cont_feats)]
y_train = as.integer(df_train$target)
X_test = df_test[,c(cat_feats, cont_feats)]
y_test = as.integer(df_test$target)

pool <- catboost.load_pool(X_train, y_train, cat_features = cat_feats)
model <- catboost.train(pool, params=list(depth = 8, iterations = 10, 
                                          loss_function='Logloss', verbose=0))

pred_train <- catboost.predict(model, catboost.load_pool(X_train), prediction_type = 'Probability')
pred_test <- catboost.predict(model, catboost.load_pool(X_test), prediction_type = 'Probability')

# feature importance
feat_importance <- catboost.get_feature_importance(model, pool)
importances <- data.frame(feat_importance[order(feat_importance, decreasing=FALSE),])
importances$features = rownames(importances)
names(importances) <- c("importance","features")
importances$features <- factor(importances$features, level=importances$features)
ggplot(importances, aes(x=importance, y=features)) + 
  geom_bar(stat="identity") +
  ggtitle("CatBoost Feature Importance")


#Shapley Values
data_shap_tree <- catboost.get_feature_importance(model, pool = pool,
                                                  type = "ShapValues")
data_shap_tree <- data.frame(data_shap_tree[, -ncol(data_shap_tree)]) 
names(data_shap_tree) = names(df[, c(cat_feats, cont_feats)])

ggplot(stack(data_shap_tree), aes(x = ind, y = values)) +
    geom_point(aes(color = values)) + coord_flip() + 
    ggtitle("Shapley Values by variable")  + scale_color_viridis_c()


results["catboost",] <- diagnosis(pred_train, pred_test, df_train$target, df_test$target)
results["catboost",]

Results and Evaluation

results[order(results$test_auc, results$test_acc),]

Although the tree-based methods are less interpretable and more “black box” to some extent, we can make use of model interpretability techniques.

It could be that our resutls are not fully robust, given we have subsampled the original data.

Conclusion

In this project, we demonstrated the use of logistic regression, gradient descent, regularisation, random forest, gradient boosting and hyperparameter tuning techniques to achieve interpretability and model accuracy (in separate cases) in predicting the amount of an insurance claim. Model ___ was the model with highest AUC, although interpretability was sacrificed. On the other hand, our baseline model with only a few predictors is easy to interpret, however it has a relatively low AUC of 0.703. In practice, depending on whether the goals of the company lean towards prediction or explanation, an appropriate trade-off between model complexity and interpretability has to be chosen.

From the insurer’s profit perspective, understanding which characteristics are highly correlated with large amounts of claims could also be used to inform whether or not a particular insurance application is accepted, even if causality cannot be inferred. However, this might lead to some legal and/or ethical issues. For example, the UK’s 2010 Equality Act makes discriminating on nine protected characteristics, including age, gender, race and religion, illegal (Pattni, 2020). Therefore, proper data governance needs to be maintained and privacy impact assessments need to be conducted before any machine learning models of this kind are deployed in industry (GDPR, 2018).

Bibliography

Chen, Tianqi and Guestrin, Carlos. 2016. “XGBoost: A Scalable Tree Boosting System.” https://arxiv.org/pdf/1603.02754.pdf.
Efron, Bradley and Hastie, Trevor. 2016. Computer Age Statistical Inference. Cambridge University Press.
Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer.
James, Gareth and Witten, Daniela and Hastie, Trevor and Robert Tibshirani. 2017. An Introduction To Statistical Learning. Springer.
Molnar, Christoph. 2019. Interpretable Machine Learning. “https://christophm.github.io/interpretable-ml-book”.
Murphy, Kevin P. 2012. Machine Learning: A Probabilistic Perspective. MIT Press. https://christophm.github.io/interpretable-ml-book.
Parr, Terence and Howard, Jeremy. 2019. The Mechanics of Machine Learning. https://mlbook.explained.ai/.
Prokhorenkova, Liudmila and Gusev, Gleb and Vorobev, Aleksandr and Dorogush, Anna Veronika and Gulin, Andrey. 2017. “CatBoost: Unbiased Boosting With Categorical Features.” https://arxiv.org/pdf/1706.09516.pdf.

Appendix

set.seed(2021)
cv_splits <- rsample::vfold_cv(df_train, strata = target, v= 3)
mod <- logistic_reg(penalty = tune(),
                    mixture = tune()) %>%
  set_engine("glmnet")

glmnet_recipe <- recipe(target~.,data = df_train) %>% 
  step_dummy(all_nominal(), -all_outcomes())

glmnet_workflow<- workflow() %>%
  add_recipe(glmnet_recipe) %>%
  add_model(mod)

glmn_set <- parameters(penalty(range = c(-5,1), trans = log10_trans()),
                       mixture())

glmn_grid <- 
  grid_regular(glmn_set, levels = c(7, 5))
ctrl <- control_grid(save_pred = TRUE, verbose = TRUE)

glmn_tune <- 
  tune_grid(glmnet_workflow,
            resamples = cv_splits,
            grid = glmn_grid,
            metrics = metric_set(roc_auc),
            control = ctrl)


best_glmn <- select_best(glmn_tune, metric = "roc_auc")

glmnet_model <- 
  logistic_reg() %>%
  set_engine("glmnet", seed=2021) %>%
  set_mode("classification")



glm3 <- fit(glmnet_workflow, data = df_train)
xgb_spec <- boost_tree(
  trees = 100, 
  tree_depth = tune(),
  learn_rate = tune()                         ## step size
) %>% 
  set_engine("xgboost") %>% 
  set_mode("classification")

xgb_grid <- grid_latin_hypercube(
  tree_depth(),
  learn_rate(),
  size = 5
)

xgb_wf <- workflow() %>%
  add_formula(target ~ .) %>%
  add_model(xgb_spec)

set.seed(123)
vb_folds <- vfold_cv(df_train, strata = target)

doParallel::registerDoParallel()

set.seed(234)
xgb_res <- tune_grid(
  xgb_wf,
  resamples = vb_folds,
  grid = xgb_grid,
  control = control_grid(save_pred = TRUE)
)
best_auc <- select_best(xgb_res, "roc_auc")
final_xgb <- finalize_workflow(
  xgb_wf,
  best_auc
)
library(vip)

final_xgb %>%
  fit(data = vb_train) %>%
  pull_workflow_fit() %>%
  vip(geom = "point")

final_res <- last_fit(final_xgb, df_split)

collect_metrics(final_res)
xgb_res %>%
  collect_metrics() %>%
  filter(.metric == "roc_auc") %>%
  select(mean, mtry:sample_size) %>%
  pivot_longer(mtry:sample_size,
               values_to = "value",
               names_to = "parameter"
  ) %>%
  ggplot(aes(value, mean, color = parameter)) +
  geom_point(alpha = 0.8, show.legend = FALSE) +
  facet_wrap(~parameter, scales = "free_x") +
  labs(x = NULL, y = "AUC")
"https://curso-r.github.io/treesnip/index.html"
library(treesnip)
LS0tCnRpdGxlOiAiU1QzMTAgQ291cnNlIFByb2plY3QiCmF1dGhvcjogIkNocmlzIENoaWEsIE11biBGYWkgQ2hhbiwgWmhlbiBZZW4gQ2hhbiIKZGF0ZTogImByIGZvcm1hdChTeXMudGltZSgpLCAnJWQvJW0vJXknKWAiCm91dHB1dDoKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIGRmX3ByaW50OiBwYWdlZAogICAga2VlcF9tZDogdHJ1ZQogIHBkZl9kb2N1bWVudDogZGVmYXVsdApoZWFkZXItaW5jbHVkZXM6Ci0gXHVzZXBhY2thZ2Uge2h5cGVycmVmfQotIFxoeXBlcnNldHVwIHtjb2xvcmxpbmtzID0gdHJ1ZSwgbGlua2NvbG9yID0gYmx1ZSwgdXJsY29sb3IgPSBibHVlfQpyZWZlcmVuY2VzOgotIGlkOiBoYXN0aWUyMDA5ZWxlbWVudHMKICB0aXRsZTogJ1RoZSBFbGVtZW50cyBvZiBTdGF0aXN0aWNhbCBMZWFybmluZzogRGF0YSBNaW5pbmcsIEluZmVyZW5jZSwgYW5kIFByZWRpY3Rpb24nCiAgYXV0aG9yOiAiSGFzdGllLCBUcmV2b3IgYW5kIFRpYnNoaXJhbmksIFJvYmVydCBhbmQgRnJpZWRtYW4sIEplcm9tZSIKICBwdWJsaXNoZXI6IFNwcmluZ2VyCiAgdHlwZTogYm9vawogIGlzc3VlZDoKICAgIHllYXI6IDIwMDkKLSBpZDogamFtZXMyMDE3aW50cm9kdWN0aW9uCiAgdGl0bGU6ICJBbiBJbnRyb2R1Y3Rpb24gVG8gU3RhdGlzdGljYWwgTGVhcm5pbmciCiAgYXV0aG9yOiAiSmFtZXMsIEdhcmV0aCBhbmQgV2l0dGVuLCBEYW5pZWxhIGFuZCBIYXN0aWUsIFRyZXZvciBhbmQgUm9iZXJ0IFRpYnNoaXJhbmkiCiAgcHVibGlzaGVyOiBTcHJpbmdlcgogIHR5cGU6IGJvb2sKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE3Ci0gaWQ6IGVmcm9uMjAxNmNvbXB1dGVyCiAgdGl0bGU6ICJDb21wdXRlciBBZ2UgU3RhdGlzdGljYWwgSW5mZXJlbmNlIgogIGF1dGhvcjogIkVmcm9uLCBCcmFkbGV5IGFuZCBIYXN0aWUsIFRyZXZvciIKICBwdWJsaXNoZXI6IENhbWJyaWRnZSBVbml2ZXJzaXR5IFByZXNzCiAgdHlwZTogYm9vawogIGlzc3VlZDoKICAgIHllYXI6IDIwMTYKLSBpZDogbW9sbmFyMjAxOQogIHRpdGxlOiAiSW50ZXJwcmV0YWJsZSBNYWNoaW5lIExlYXJuaW5nIgogIGF1dGhvcjogIk1vbG5hciwgQ2hyaXN0b3BoIgogIHR5cGU6IGJvb2sKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE5CiAgVVJMOiDigJxodHRwczovL2NocmlzdG9waG0uZ2l0aHViLmlvL2ludGVycHJldGFibGUtbWwtYm9va+KAnQotIGlkOiBtdXJwaHkyMDEybWFjaGluZQogIHRpdGxlOiAiTWFjaGluZSBMZWFybmluZzogQSBQcm9iYWJpbGlzdGljIFBlcnNwZWN0aXZlIgogIGF1dGhvcjogIk11cnBoeSwgS2V2aW4gUC4iCiAgcHVibGlzaGVyOiBNSVQgUHJlc3MKICB0eXBlOiBib29rCiAgaXNzdWVkOgogICAgeWVhcjogMjAxMgogIFVSTDogImh0dHBzOi8vY2hyaXN0b3BobS5naXRodWIuaW8vaW50ZXJwcmV0YWJsZS1tbC1ib29rIgotIGlkOiBwcm9raG9yZW5rb3ZhMjAxN2NhdGJvb3N0CiAgdGl0bGU6ICJDYXRCb29zdDogVW5iaWFzZWQgQm9vc3RpbmcgV2l0aCBDYXRlZ29yaWNhbCBGZWF0dXJlcyIKICB0eXBlOiBhcnRpY2xlLWpvdXJuYWwKICBhdXRob3I6ICJQcm9raG9yZW5rb3ZhLCBMaXVkbWlsYSBhbmQgR3VzZXYsIEdsZWIgYW5kIFZvcm9iZXYsIEFsZWtzYW5kciBhbmQgRG9yb2d1c2gsIEFubmEgVmVyb25pa2EgYW5kIEd1bGluLCBBbmRyZXkiCiAgaXNzdWVkOgogICAgeWVhcjogMjAxNwogIFVSTDogImh0dHBzOi8vYXJ4aXYub3JnL3BkZi8xNzA2LjA5NTE2LnBkZiIKLSBpZDogY2hlbjIwMTZ4Z2Jvb3N0CiAgdGl0bGU6ICJYR0Jvb3N0OiBBIFNjYWxhYmxlIFRyZWUgQm9vc3RpbmcgU3lzdGVtIgogIGF1dGhvcjogIkNoZW4sIFRpYW5xaSBhbmQgR3Vlc3RyaW4sIENhcmxvcyIKICB0eXBlOiBhcnRpY2xlLWpvdXJuYWwKICBpc3N1ZWQ6CiAgICB5ZWFyOiAyMDE2CiAgVVJMOiAiaHR0cHM6Ly9hcnhpdi5vcmcvcGRmLzE2MDMuMDI3NTQucGRmIgotIGlkOiBwYXJyMjAxOW1vbWwKICB0aXRsZTogIlRoZSBNZWNoYW5pY3Mgb2YgTWFjaGluZSBMZWFybmluZyIKICBhdXRob3I6ICJQYXJyLCBUZXJlbmNlIGFuZCBIb3dhcmQsIEplcmVteSIKICB0eXBlOiBib29rCiAgaXNzdWVkOgogICAgeWVhcjogMjAxOQogIFVSTDogImh0dHBzOi8vbWxib29rLmV4cGxhaW5lZC5haS8iCi0tLQoKIyBTVDMxMCBDb3Vyc2UgUHJvamVjdAoKVGhlIGFpbSBvZiB0aGlzIHByb2plY3QgaXMgdG8gZGVtb25zdHJhdGUgdGhlIHVzZSBvZiBtYWNoaW5lIGxlYXJuaW5nIHRlY2huaXF1ZXMgZGlzY3Vzc2VkIGluIHRoZSBTVDMxMCBNYWNoaW5lIExlYXJuaW5nIG1vZHVsZSwgaW4gdHVybiBwcmltYXJpbHkgZHJhd2luZyBmcm9tIFtAamFtZXMyMDE3aW50cm9kdWN0aW9uXSBhbmQgW0BoYXN0aWUyMDA5ZWxlbWVudHNdLiBXZSByZWx5IG9uIGJvdGggbGluZWFyIChMb2dpc3RpYyBSZWdyZXNzaW9uKSBhbmQgbm9uLWxpbmVhciBtZXRob2RzIChSYW5kb20gRm9yZXN0cyBhbmQgR3JhZGllbnQgQm9vc3RlZCBEZWNpc2lvbiBUcmVlcykgZm9yIGEgY2xhc3NpZmljYXRpb24gcHJvYmxlbS4KIAoqKlJlbWFyayoqOiBJZiBleGVjdXRpbmcgdGhpcyBub3RlYm9va3MgYXMgYSBgLlJtZGAgZmlsZSwgZW5zdXJlIHRoYXQgYWxsIGxpYnJhcmllcyBhbmQgZGVwZW5kZW5jaWVzIGFyZSBpbnN0YWxsZWQgYW5kIHRoYXQgdGhlIGNodW5rcyBhcmUgZXhlY3V0ZWQgaW4gc2VxdWVudGlhbCBvcmRlci4KCgojIyBEYXRhc2V0IAoKV2UgaGF2ZSBvYnRhaW5lZCBkYXRhIGZyb20gdGhlIFtLYWdnbGUgTWFyY2ggVGFidWxhciBQbGF5Z3JvdW5kXSgjaHR0cHM6Ly93d3cua2FnZ2xlLmNvbS9jL3RhYnVsYXItcGxheWdyb3VuZC1zZXJpZXMtbWFyLTIwMjEvb3ZlcnZpZXcpIGNvbXBldGl0aW9uLiBUaGUgZGF0YSBjb25zaXN0cyBvZiAqYW5vbnltaXNlZCBmZWF0dXJlcyosIHdoaWNoIGNvcnJlc3BvbmQgdG8gYSBiaW5hcnkgb3V0Y29tZSB2YXJpYWJsZTsgaW4gb3RoZXIgd29yZHMgdGhlIHRhc2sgaXMgYSAqKmNsYXNzaWZpY2F0aW9uIHByb2JsZW0qKi4gQWx0aG91Z2ggdGhlIGRhdGEgaXMgYW5vbnltaXNlZCwgdGhlIGNoYWxsZW5nZSBkZXNjcmlwdGlvbiBzdGF0ZXM6Cgo+IFRoZSBkYXRhc2V0IHVzZWQgZm9yIHRoaXMgY29tcGV0aXRpb24gaXMgc3ludGhldGljIGJ1dCBiYXNlZCBvbiBhIHJlYWwgZGF0YXNldCBhbmQgZ2VuZXJhdGVkIHVzaW5nIGEgQ1RHQU4uIFRoZSBvcmlnaW5hbCBkYXRhc2V0IGRlYWxzIHdpdGggcHJlZGljdGluZyB0aGUgYW1vdW50IG9mIGFuIGluc3VyYW5jZSBjbGFpbS4gQWx0aG91Z2ggdGhlIGZlYXR1cmVzIGFyZSBhbm9ueW1pemVkLCB0aGV5IGhhdmUgcHJvcGVydGllcyByZWxhdGluZyB0byByZWFsLXdvcmxkIGZlYXR1cmVzLgoKV2UgYmVsaWV2ZSB0aGF0IHRoaXMgbWFjaGluZSBsZWFybmluZyB0YXNrIGlzIHdlbGwtbW90aXZhdGVkIGFzIHByZWRpY3RpbmcgdGhlIGFtb3VudCBvZiBhbiBpbnN1cmFuY2UgY2xhaW0sIG9yIHdoZXRoZXIgYW4gaW5zdXJhbmNlIGNsYWltIG9jY3VyZWQsIHdvdWxkIGJlIHVzZWZ1bCBmb3IgaGVscGluZyBhbiBpbnN1cmFuY2UgY29tcGFueSBmb3JlY2FzdCBpdHMgY2FzaCBmbG93IGFuZCBtYW5hZ2Ugcmlzay4gCgpUaGUgZGF0YXNldCBjb25zaXN0cyBvZiAzMCBmZWF0dXJlcywgIDE5ICpjYXRlZ29yaWNhbCB2YXJpYWJsZXMqIGFuZCAxMSBudW1lcmljYWwgdmFyaWFibGVzLiwgYW5kIGEgYmluYXJ5IG91dGNvbWUgdmFyaWFibGUgYHRhcmdldGAuIDczLjUlIG9mIHRoZSBvYnNlcnZhdGlvbnMgaGF2ZSDigJh0YXJnZXQ9PTHigJksIHN1Z2dlc3RpbmcgYW4gKmltYmFsYW5jZWQgZGF0YXNldCouIFdlIHdpbGwgbmVlZCB0byBwcm9jZXNzIHRoZXNlIGNhdGVnb3JpY2FsIHZhcmlhYmxlcyBpbiBzb21lIG1hbm5lciwgd2hpY2ggd2Ugc2hhbGwgY29uc2lkZXIgaW4gW3N1YnNlcXVlbnQgc2VjdGlvbnNdKCNwcmVwcm9jZXNzaW5nKS4KCkEgY2hhbGxlbmdlIGlzIHRoYXQgd2UgaGF2ZSBubyAqc3BlY2lmaWMqIGRvbWFpbiBrbm93bGVkZ2UgYWJvdXQgdGhlIG1lYW5pbmcgb2YgcGFydGljdWxhciBmZWF0dXJlcywgYW5kIHdoZXRoZXIgdGhleSBtYXkgYmUgdXNlZnVsLiBOb25ldGhlbGVzcywgd2UgY2FuIHJlc29ydCB0byBtb2RlbCBpbnRlcnByZXRhYmlsaXR5IG1ldGhvZHMgW0Btb2xuYXIyMDE5XSB0byBvYnRhaW4gYW4gZXgtcG9zdCBleHBsYW5hdGlvbiBvZiBvdXIgbW9kZWxzLiBJbiB0aGUgbGluZWFyIGNhc2UsIHdlIGNhbiBleGFtaW5lIGNvZWZmaWNpZW50cyBhbmQgdGhlaXIgc3RhdGlzdGljYWwgc2lnbmlmaWNhbmNlLCBhbmQgaW4gdGhlIGNhc2Ugb2YgdHJlZS1iYXNlZCBtb2RlbHMsIHN1Y2ggYXMgZmVhdHVyZSBpbXBvcnRhbmNlcywgcGFydGlhbCBkZXBlbmRlbmNlIHBsb3RzLCBhbmQgU2hhcGxleSBWYWx1ZXMuCgoKCgpgYGB7ciBsb2FkLWxpYnMsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoR0dhbGx5KQpsaWJyYXJ5KHBhdGNod29yaykKbGlicmFyeShicm9vbSkKbGlicmFyeSh0aWR5bW9kZWxzKQpsaWJyYXJ5KGFybSkKbGlicmFyeShjYXIpICNvdXRsaWVyCmxpYnJhcnkodGlkeXIpCmxpYnJhcnkoZ2xtbmV0KQpsaWJyYXJ5KGNhcmV0KQpsaWJyYXJ5KHJhbmRvbUZvcmVzdCkKbGlicmFyeSh4Z2Jvb3N0KQpsaWJyYXJ5KGNhdGJvb3N0KQpsaWJyYXJ5KGUxMDcxKQpsaWJyYXJ5KGRhdGEudGFibGUpCmxpYnJhcnkoZG9QYXJhbGxlbCkKbGlicmFyeShmb3JlYWNoKQpsaWJyYXJ5KHBST0MpCmxpYnJhcnkocGRwKQpkZiA8LSByZWFkLmNzdihmaWxlID0gIi4uL2RhdGEvdHJhaW4uY3N2IikKY2F0KGMoIlRoZSBkaW1lbnNpb25zIG9mIHRoZSBhcnJheSBhcmUgOiIsIGRpbShkZilbMV0sICIsICIsIGRpbShkZilbMl0pKQpgYGAKVGhlIGRhdGFzZXQgY29uc2lzdHMgb2YgMzAgZmVhdHVyZXMsICAxOSAqY2F0ZWdvcmljYWwgdmFyaWFibGVzKiBhbmQgMTEgbnVtZXJpY2FsIHZhcmlhYmxlcy4sIGFuZCBhIGJpbmFyeSBvdXRjb21lIHZhcmlhYmxlIGB0YXJnZXRgLiBXZSB3aWxsIG5lZWQgdG8gcHJvY2VzcyB0aGVzZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgaW4gc29tZSBtYW5uZXIsIHdoaWNoIHdlIHNoYWxsIGNvbnNpZGVyIGluIHRoZSBbc3Vic2VxdWVudCBzZWN0aW9uXSgjcHJlcHJvY2Vzc2luZykuCgpBIGNoYWxsZW5nZSBpcyB0aGF0IHdlIGhhdmUgbm8gKnNwZWNpZmljKiBkb21haW4ga25vd2xlZGdlIGFib3V0IHRoZSBtZWFuaW5nIG9mIHBhcnRpY3VsYXIgZmVhdHVyZXMsIGFuZCB3aGV0aGVyIHRoZXkgbWF5IGJlIHVzZWZ1bC4gTm9uZXRoZWxlc3MsIHdlIGNhbiByZXNvcnQgdG8gbW9kZWwgaW50ZXJwcmV0YWJpbGl0eSBtZXRob2RzIFtAbW9sbmFyMjAxOV0gdG8gb2J0YWluIGFuIGV4LXBvc3QgZXhwbGFuYXRpb24gb2Ygb3VyIG1vZGVscy4gSW4gdGhlIGxpbmVhciBjYXNlLCB3ZSBjYW4gZXhhbWluZSBjb2VmZmljaWVudHMgYW5kIHRoZWlyIHN0YXRpc3RpY2FsIHNpZ25pZmljYW5jZSwgYW5kIGluIHRoZSBjYXNlIG9mIHRyZWUtYmFzZWQgbW9kZWxzLCB3ZSBjYW4gdXRpbGlzZSBmZWF0dXJlIGltcG9ydGFuY2VzLCBwYXJ0aWFsIGRlcGVuZGVuY2UgcGxvdHMsIGFuZCBTaGFwbGV5IFZhbHVlcy4KCiMjIFByZXByb2Nlc3NpbmcKV2UgcmVtb3ZlIHRoZSBmaXJzdCBjb2x1bW4gYGlkYCwgd2hpY2ggcmVwcmVzZW50cyBhbiB1bmlxdWUgaWRlbnRpZmllciBmb3IgZWFjaCBvYnNlcnZhdGlvbi4gV2UgdGhlbiBjb252ZXJ0IHRoZSBmaXJzdCAxOSBjb2x1bW5zLCB3aGljaCBhcmUgY2F0ZWdvcmljYWwgdmFyaWFibGVzIGludG8gdGhlICpmYWN0b3IqIGRhdGEgdHlwZSBpbiBSLCBUbyByZWR1Y2UgY29tcHV0YXRpb25hbCB0aW1lLCB3ZSBzdWJzYW1wbGUgNDAwMCBvYnNlcnZhdGlvbnMgZnJvbSB0aGUgY29tcGxldGUgZGF0YXNldCBvZiAzMDAsMDAwIG9ic2VydmF0aW9ucy4gRm9yIG91ciBzdWJzZXF1ZW50IGFuYWx5c2lzLCB3ZSB3aWxsIHVzZSBvbmx5IHRoaXMgc3Vic2FtcGxlIG9mIDQwMDAgb2JzZXJ2YXRpb25zLCBhbHRob3VnaCB0aGUgYXBwcm9hY2hlcyBjYW4gYmUgZXh0ZW5kZWQgdG8gYSBsYXJnZXIgZGF0YXNldCBnaXZlbiBncmVhdGVyIGNvbXB1dGF0aW9uYWwgcmVzb3VyY2VzLiAgV2UgZnVydGhlciBwYXJ0aXRpb24gdGhlIDQwMDAgb2JzZXJ2YXRpb25zLCBpbnRvIGEgdHJhaW4gc2V0IG9mIDMwMDAgb2JzZXJ2YXRpb25zIGFuZCBhIHRlc3Qgc2V0IG9mICAxMDAwIG9ic2VydmF0aW9ucy4gQWxsIHRyYWluaW5nIGFuZCB0dW5pbmcgYXJlIHBlcmZvcm1lZCBvbiB0aGUgdHJhaW5pbmcgZGF0YSwgYW5kIHdlIHdpbGwgY29uc2lkZXIgbW9kZWwgcGVyZm9ybWFuY2Ugb24gdGhlIHRlc3Qgc2V0IHBlcmZvcm1hbmNlIHNjb3Jlcy4KCioqUmVtYXJrKio6IERpZmZlcmVudCBtb2RlbHMgd291bGQgcmVxdWlyZSBkaWZmZXJlbnQgcHJlcHJvY2Vzc2luZyBmb3IgdGhlIGNhdGVnb3JpY2FsIHZhcmlhYmxlcywgYW5kIHRodXMgd2Ugd2lsbCBmdXJ0aGVyIGFkZHJlc3MgaW4gc3Vic2VxdWVudCBzZWN0aW9uczsgZm9yIGV4YW1wbGUgdGhlIGBnbG1gIHBhY2thZ2UgY2FuIGFjY2VwdCAqZmFjdG9ycyogYXMgYSBkYXRhIHR5cGUsIHdoZXJlYXMgZm9yIGBnbG1uZXRgIHRoZXkgbXVzdCBiZSBjb252ZXJ0ZWQgdG8gdGhlIG1vZGVsLm1hdHJpeCBmb3JtYXQuCgoqKlJlbWFyayoqOiBXaGVuIGVuY29kaW5nIHRoZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgYXMgZHVtbXkgdmFyaWFibGVzIGluIG91ciBzdWJzZXF1ZW50IGFuYWx5c2lzLCB3ZSBmaW5kIHRoYXQgdGhlcmUgYXJlIG92ZXIgNjAwIHVuaXF1ZSBjYXRlZ29yaWVzIGFjcm9zcyBhbGwgMTkgb2YgdGhlIGNhdGVnb3JpY2FsIHZhcmlhYmxlcy4gIFdlIGNvdWxkIGFsc28gY29uc2lkZXIgZGlmZmVyZW50IG1ldGhvZHMgdG8gcHJvY2VzcyBjYXRlZ29yaWNhbCB2YXJpYWJsZXMsIHN1Y2ggYXMgbWVyZ2luZyBsZXNzIGZyZXF1ZW50bHkgb2NjdXJpbmcgY2F0ZWdvcmllcywgb3IgICp0YXJnZXQgZW5jb2RpbmcqIFtAcGFycjIwMTltb21sLCBjaC4gNl0uIE5vbmV0aGVsZXNzLCB3ZSBzdGljayB3aXRoIHRoZSBmYWN0b3JzIGFuZCBkdW1taWVzIGFwcHJvYWNoIGdpdmVuIG91ciBsYWNrIG9mIGZhbWlsaWFyaXR5IHdpdGggdGhlc2Ugb3RoZXIgbWV0aG9kcy4KCgoKYGBge3IgcGFydGl0aW9ufQpjYXRfZmVhdHMgPSAxOjE5ICMgdGhlIGZpcnN0IDE5IGNvbHVtbnMgYXJlIGNhdGVnb3JpY2FsIApjb250X2ZlYXRzIDwtIDIwOjMwICMgYW5kIHRoZSBuZXh0IDExIGFyZSBjb250aW51b3VzCnRhcmdldF9jb2wgPC0gMzEgIyB0YXJnZXQKIyBjb252ZXJ0IGNhdHMgdG8gZmFjdG9ycwpkZiA8LSBjb2x1bW5fdG9fcm93bmFtZXMoZGYsIHZhciA9ICJpZCIpICU+JSAKICAgICAgICAgbXV0YXRlX2lmKGlzLmNoYXJhY3Rlcixhcy5mYWN0b3IpICU+JSAKICAgICAgICAgbXV0YXRlX2F0KHZhcnModGFyZ2V0KSwgZmFjdG9yKQojIHN1YnNhbXBsZSB0aGUgZGF0YSBmb3IgZmFzdGVyIG1vZGVsIGltcHV0YXRpb24Kc2V0LnNlZWQoMSkKc2FtID0gc2FtcGxlKDE6bnJvdyhkZiksIDQwMDApCmRmX3NhbXBsZSA9IGRmW3NhbSxdCiMgUGFydGl0aW9uIGRhdGEgaW50byB0cmFpbiBhbmQgdGVzdDsgdGVzdCB3aWxsIGJlIG91ciBvb3MgZGF0YQpzZXQuc2VlZCgxKQpkZl9zcGxpdCA8LSBpbml0aWFsX3NwbGl0KGRmX3NhbXBsZSwgcHJvcCA9IDMvNCkKZGZfdHJhaW4gPC0gdHJhaW5pbmcoZGZfc3BsaXQpCmRmX3Rlc3QgPC0gdGVzdGluZyhkZl9zcGxpdCkKYGBgCgojIyBFeHBsb3JhdG9yeSBEYXRhIEFuYWx5c2lzCgojIyMgVW5pdmFyaWF0ZSBFREEKV2Ugb2JzZXJ2ZSB0aGF0IHRoZSB1bml2YXJpYXRlIGRpc3RyaWJ1dGlvbnMgb2YgdGhlICpjb250aW51b3VzKiB2YXJpYWJsZXMgYXJlIGFsbCBtdWx0aS1tb2RhbCBhbmQgbm9uLW5vcm1hbCwgYnV0IHRoZXkgYXJlIGFsbCBub3JtYWxpc2VkIHRvIHRoZSByYW5nZSBvZiAkWzAsIDFdJC4KYGBge3IgY29udC12aXp9CiMgZmxhdHRlbiBkZiBpbnRvIHVzaW5nIHBpdm90X2xvbmdlciBhbmQgcGxvdCBkaXN0cmlidXRpb24KZGYgJT4lIHBpdm90X2xvbmdlcihjb2xzID0gc3RhcnRzX3dpdGgoImNvbnQiKSwgbmFtZXNfdG8gID0gImNvbnQiKSAlPiUgCiAgIGdncGxvdChhZXMoeCA9IHZhbHVlKSkrCiAgIGdlb21faGlzdG9ncmFtKGJpbnMgPSAxMDAsIGFscGhhID0gMC44NSkrCiAgIGdndGl0bGUoIkNvbnRpbnVvdXMgZmVhdHVyZXMgZGlzdHJpYnV0aW9uIikrCiAgIGZhY2V0X3dyYXAoY29udH4uLHNjYWxlcyA9ICJmcmVlIikgKwogICB0aGVtZV9taW5pbWFsKCkKYGBgCkZyb20gdGhlIGRpc3RyaWJ1dGlvbnMgb2YgY2F0ZWdvcmljYWwgdmFyaWFibGVzLCB3ZSBzZWUgdGhhdCB0aGVyZSBhcmUgdmFyaWFibGVzIHdpdGggc3Vic3RhbnRpYWxseSBtb3JlIG9ic2VydmF0aW9ucyBpbiBvbmUgY2F0ZWdvcnksIGFuZCBhbHNvIHZhcmlhYmxlcyB3aXRoIGEgaGlnaCBudW1iZXIgb2YgKCQ+NTAkKSBjYXRlZ29yaWVzLCB3aGljaCB3aWxsIGJlIGFuIGlzc3VlIHRvIGFkZHJlc3MgaW4gc3Vic2VxdWVudCBwcmVwcm9jZXNzaW5nLiAKYGBge3IgY2F0LXZpeiwgZmlnLndpZHRoPTE1LCBmaWcuaGVpZ2h0PTE1fQojIGZsYXR0ZW4gZGYgaW50byB1c2luZyBwaXZvdF9sb25nZXIgYW5kIHBsb3QgZGlzdHJpYnV0aW9uCmRmICU+JSBwaXZvdF9sb25nZXIoY29scyA9IGNvbnRhaW5zKGMoImNhdCIsICJ0YXJnZXQiKSksIG5hbWVzX3RvICA9ICJjYXQiKSAlPiUgCiAgIGdncGxvdChhZXMoeCA9IHZhbHVlKSkrCiAgIGdlb21fYmFyKGFscGhhID0gMC44NSkrCiAgIGdndGl0bGUoIkNhdGVnb3JpY2FsIGZlYXR1cmVzIGRpc3RyaWJ1dGlvbiIpKwogICBmYWNldF93cmFwKGNhdH4uLHNjYWxlcyA9ICJmcmVlIiwgbmNvbCA9IDQpICsKICAgdGhlbWVfbWluaW1hbChiYXNlX3NpemUgPSAzMCkKYGBgCgoKCiMjIyBCaXZhcmlhdGUgRURBCgpXZSBncm91cCB0aGUgY29udGludW91cyB2YXJpYWJsZXMgYnkgdGhlIHRhcmdldCBhbmQgcGxvdCB0aGVtIGFzIGJveHBsb3RzIHRvIGNoZWNrIGZvciBhbnkgb2J2aW91cyBkaWZmZXJlbmNlcyBkaXNjZXJuaWJsZSBieSBleWUuIEZyb20gdGhlIHBsb3RzLCBjbGFpbXMgd2l0aCBgdGFyZ2V0ID09IDFgIGhhdmUgbG93ZXIgdmFsdWVzIG9mIGBjb250M2Agb24gYXZlcmFnZSAobWVkaWFuKSB0aGFuIGNsYWltcyB3aXRoIGB0YXJnZXQgPT0gMGAuIENsYWltcyB3aXRoIHRhcmdldD0xIGFsc28gaGF2ZSBhIG11Y2ggaGlnaGVyIG1lZGlhbiB2YWx1ZSBvZiBjb250NCB0aGFuIGNsYWltcyB3aXRoIGB0YXJnZXQgPT0gMGAuIEhlbmNlLCB3ZSB3b3VsZCBleHBlY3QgYGNvbnQzYCBhbmQgYGNvbnQ0YCB0byBoYXZlIG5lZ2F0aXZlIHJlbGF0aW9uc2hpcHMgd2l0aCB0YXJnZXQuIEluIGFkZGl0aW9uLCB3ZSBzZWUgYSBncm91cCBvZiBvYnNlcnZhdGlvbnMgYXQgdGhlIHRhaWwgZW5kcyBmb3IgYGNvbnQwLCBjb250NSwgY29udDcsIGNvbnQ4LCBjb250OSwgY29udDEwYCwgd2hpY2ggbWF5IGJlIGluZGljYXRpdmUgb2Ygb3V0bGllcnMuIFRoaXMgd2lsbCBiZSBhZGRyZXNzZWQgYXQgdGhlIGVuZCBvZiB0aGlzIHNlY3Rpb24uCgpgYGB7ciBjb250LWJ5LXRhcmdldH0KIyBmbGF0dGVuIGRmIGludG8gdXNpbmcgcGl2b3RfbG9uZ2VyCiMgZ3JvdXAgYnkgdGFyZ2V0IGFuZCBwbG90IGRpc3RyaWJ1dGlvbgpkZlssIGMoY29udF9mZWF0cywgdGFyZ2V0X2NvbCldICU+JSAKICBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJjb250IiksIG5hbWVzX3RvICA9ICJ2YXIiLCB2YWx1ZXNfdG89InZhbHVlIikgJT4lIAogIGdncGxvdChhZXMoeD10YXJnZXQseT12YWx1ZSksIGZpbGw9ZmFjdG9yKHZhbHVlKSkgKyAKICBnZW9tX2JveHBsb3QoKSArIGNvb3JkX2ZsaXAoKSArIGZhY2V0X3dyYXAofnZhciwgc2NhbGVzPSJmcmVlX3giKQpgYGAKCkZyb20gb3VyIGNvbmRpdGlvbmFsIGJveHBsb3RzLCB3ZSBjYW4gaWRlbnRpZnkgcG90ZW50aWFsIG91dGxpZXJzLiBJbiBwYXJ0aWN1bGFyIHdlIGNhbiBzcG90IG1hbnkgcG90ZW50aWFsIG91dGxpZXJzIGZvciBgY29udDAsIGNvbnQ1LCBjb250NywgY29udDgsIGNvbnQ5IGFuZCBjb250MTBgLiBXZSBpbnZlc3RpZ2F0ZSB0aGUgcG90ZW50aWFsIG91dGxpZXJzIHNwb3R0ZWQgaW4gdGhlIGJpdmFyaWF0ZSBwbG90cyBieSBpZGVudGlmeWluZyBvYnNlcnZhdGlvbnMgdGhhdCBsaWUgYXQgdGhlIGV4dHJlbWUgcGVyY2VudGlsZXMgb2YgdGhvc2UgY29udGludW91cyB2YXJpYWJsZXMuIFVzaW5nIHRoZSBIYW1wZWwgZmlsdGVyLCB3aGljaCBjb25zaWRlcnMgcG9pbnRzIGx5aW5nIG91dHNpZGUgdGhlIG1lZGlhbiBwbHVzIG9yIG1pbnVzIDMgbWVhbiBhYnNvbHV0ZSBkZXZpYXRpb25zIGFzIG91dGxpZXJzLCBtb3JlIHRoYW4gMjAwIG9ic2VydmF0aW9ucyBwZXIgdmFyaWFibGUgd2VyZSBjbGFzc2lmaWVkIGFzIHN1Y2guIFRoaXMgc3VnZ2VzdHMgdGhhdCB0aGVzZSBtYXkgbm90IGJlIG91dGxpZXJzIGJ1dCB0aGF0IHRoZSBkaXN0cmlidXRpb24gaXMganVzdCBoZWF2eS10YWlsZWQuIFdpdGhvdXQgZnVydGhlciBpbmZvcm1hdGlvbiBvbiB0aGUgcmVhc29uYWJsZSBzY2FsZSBvZiB2YWx1ZXMgdGhhdCBpbmRpdmlkdWFsIHZhcmlhYmxlcyBjYW4gdGFrZSAoYWxvbmcgd2l0aCB0aGUgZmFjdCB0aGF0IHRoZXkgYXJlIGFsbCBub3JtYWxpc2VkKSwgd2UgZmluZCBpdCBjaGFsbGVuZ2luZyB0byBpZGVudGlmeSBvdXRsaWVycyB0aHJvdWdoIGRlc2NyaXB0aXZlIHN0YXRpc3RpY3MgYW5kIGRlY2lkZSBub3QgdG8gZXhjbHVkZSBhbnkgc3VjaCBwb2ludHMgdXNpbmcgdGhpcyBhcHByb2FjaC4gV2Ugd2lsbCBwcm9jZWVkIHRvIGRldGVjdCBvdXRsaWVycyBpbiBhbm90aGVyIGFwcHJvYWNoIGluIFtzZWN0aW9uIDNiXS4KCgpgYGB7cn0KaGFtcGVsX2ZpbHRlciA8LSBmdW5jdGlvbihkZil7CiAgIGxvd2VyX2JvdW5kIDwtIG1lZGlhbihkZikgLSAzICogbWFkKGRmLCBjb25zdGFudCA9IDEpCiAgIHVwcGVyX2JvdW5kIDwtIG1lZGlhbihkZikgKyAzICogbWFkKGRmLCBjb25zdGFudCA9IDEpCiAgIG91dGxpZXJfaW5kIDwtIHdoaWNoKGRmIDwgbG93ZXJfYm91bmQgfCBkZiA+IHVwcGVyX2JvdW5kKQogICByZXR1cm4ob3V0bGllcl9pbmQpCn0KcGVyY2VudGlsZV9maWx0ZXIgPC0gZnVuY3Rpb24oZGYsIGxxID0gMC4wMDEsIHVxID0gMC45OTkpewogICBsb3dlcl9ib3VuZCA8LSBxdWFudGlsZShkZiwgbHEpCiAgIHVwcGVyX2JvdW5kIDwtIHF1YW50aWxlKGRmLCB1cSkKICAgb3V0bGllcl9pbmQgPC0gd2hpY2goZGYgPCBsb3dlcl9ib3VuZCB8IGRmID4gdXBwZXJfYm91bmQpCiAgIHJldHVybihvdXRsaWVyX2luZCkKfQpoYW1wZWxfY291bnQgPC0gZnVuY3Rpb24oeCl7bGVuZ3RoKGhhbXBlbF9maWx0ZXIoeCkpfQpwY3RfY291bnQgPC0gZnVuY3Rpb24oeCl7bGVuZ3RoKHBlcmNlbnRpbGVfZmlsdGVyKHgpKX0KCm91dGxpZXJfY291bnRzIDwtIGRmX3RyYWluWywgY29udF9mZWF0c10gJT4lIG1hcF9kZnIoaGFtcGVsX2NvdW50KQpvdXRsaWVyX2NvdW50c1syLCBdIDwtIGRmX3RyYWluWywgY29udF9mZWF0c10gJT4lIG1hcF9kZnIocGN0X2NvdW50KQpvdXRsaWVyX2NvdW50cwpgYGAKRm9yIGNhdGVnb3JpY2FsIHZhcmlhYmxlcywgd2UgdXNlIHN0YWNrZWQgYmFyIHBsb3RzIHRvIHNob3cgdGhlIHBlcmNlbnRhZ2VzIG9mIG9ic2VydmF0aW9ucyBpbiBlYWNoIGNhdGVnb3J5IHRoYXQgY29ycmVzcG9uZCB0byBgdGFyZ2V0ID09IDBgIGFuZCBgdGFyZ2V0ID09IDFgIHJlc3BlY3RpdmVseS4gQSBtdWNoIGxhcmdlciBwcm9wb3J0aW9uIG9mIGNsYWltcyB3aXRoIGBjYXQxMyA9PSBCYCBhcHBlYXIgdG8gYmUgYXNzb2NpYXRlZCB3aXRoIGB0YXJnZXQgPT0gMWAgY29tcGFyZWQgdG8gYGNhdDEzID09IEFgLiBPbiB0aGUgb3RoZXIgaGFuZCwgYSBtdWNoIGxhcmdlciBwZXJjZW50YWdlIG9mIGNsYWltcyBjb3JyZXNwb25kIHRvIGB0YXJnZXQgPT0gMGAgaWYgYGNhdDE4YCBpcyBgQWAgb3IgYEJgLCB0aGFuIGlmIGBjYXQxOGAgaXMgYENgIG9yIGBEYC4KCmBgYHtyIGNhdC1ieS10YXJnZXQsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0UsIGZpZy53aWR0aD0xNSwgZmlnLmhlaWdodD0xNX0KIyBmbGF0dGVuIGRmIGludG8gdXNpbmcgcGl2b3RfbG9uZ2VyCiMgZ3JvdXAgYnkgdGFyZ2V0IGFuZCBwbG90IGRpc3RyaWJ1dGlvbgpkZlssIGMoY2F0X2ZlYXRzLCB0YXJnZXRfY29sKV0gJT4lIAogIHBpdm90X2xvbmdlcihjb2xzID0gc3RhcnRzX3dpdGgoImNhdCIpLCBuYW1lc190byAgPSAiY2F0IiwgdmFsdWVzX3RvPSJ2YWx1ZSIpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSB2YWx1ZSwgZmlsbD10YXJnZXQpKSArIAogICAgZ2VvbV9iYXIocG9zaXRpb249ImZpbGwiKSArIAogICAgc2NhbGVfeV9jb250aW51b3VzKG5hbWUgPSAiV2l0aGluIGdyb3VwIFBlcmNlbnRhZ2UiLCBsYWJlbHMgPSBzY2FsZXM6OnBlcmNlbnQpICsKICAgIGZhY2V0X3dyYXAofmNhdCwgc2NhbGVzPSJmcmVlX3giLCBuY29sID0gNCkgKwogICAgdGhlbWVfbWluaW1hbChiYXNlX3NpemUgPSA0MCkKYGBgCgpXZSBhbHNvIGluc3BlY3QgdGhlIGNvcnJlbGF0aW9uIG1hdHJpeCBmb3Igb3VyICpjb250aW51b3VzKiB2YXJpYWJsZXMuIFRoZXJlIHNlZW1zIHRvIGJlIGEgY2x1c3RlciBvZiB2YXJpYWJsZXMgLSBgY29udDEsIGNvbnQyLCBjb250OGAgLSB0aGF0IGFyZSBoaWdobHkgY29ycmVsYXRlZCB3aXRoIGVhY2ggb3RoZXIuIFRoaXMgbWF5IGJlIHBvdGVudGlhbGx5IGluZGljYXRpdmUgb2YgbXVsdGljb2xsaW5lYXJpdHksIGEgY29uY2VybiB3aGVuIHVzaW5nIGxpbmVhciBtb2RlbHMuIEluIGFkZGl0aW9uLCB3ZSBhbHNvIGNvbnNpZGVyIHRoZSAoUGVhcnNvbikgY29ycmVsYXRpb24gYW5kIG91ciBjb250aW51b3VzIHZhcmlhYmxlcywgYWx0aG91Z2ggaXQgaXMgbm90IG5lY2Vzc2FyaWx5IG1lYW5pbmdmdWwgaW4gdGhpcyBjYXNlIGdpdmVuIG91ciB0YXJnZXQgaXMgYmluYXJ5LiBIb3dldmVyLCB3ZSBub3RlIHRoYXQgdGhlIGNvbnRpbnVvdXMgdmFyaWFibGVzIGhhdmUgUGVhcnNvbiBjb3JyZWxhdGlvbnMgb2Ygcm91Z2hseSAkWy0wLjIsIDAuMl0kLCBzdWdnZXN0aW5nIHRoYXQgdGhlcmUgaXMgc29tZSBzaWduYWwgKGluIHRoZSBmb3JtIG9mICppbmZvcm1hdGlvbiogb3IgYW4gKmFzc29jaWF0aW9uKikgYmV0d2VlbiB0aGUgZmVhdHVyZXMgYW5kIHRoZSB0YXJnZXQuIFdlICBzaG91bGQgbm90ZSB0aGF0IHRoZSBwZWFyc29uIGNvcnJlbGF0aW9uIG9ubHkgZGVzY3JpYmVzIGEgKmxpbmVhciogYW5kICpwYWlyd2lzZSogYXNzb2NpYXRpb24gYmV0d2VlbiB0aGUgdmFyaWFibGVzLiBBcyBzdWNoIHRoZXJlIGNvdWxkIGJlIGNvbXBsZXggbm9uLWxpbmVhciBhc3NvY2lhdGlvbnMgYW5kIGludGVyYWN0aW9ucyBiZXR3ZWVuIHRoZSB2YXJpYWJsZXMgYXMgd2VsbCwgd2hpY2ggdGhlIHByZXNlbmNlIG9mIG11bHRpLW1vZGFsIGRpc3RyaWJ1dGlvbnMgb2YgdGhlIGNvbnRpbnVvdXMgZmVhdHVlcnMgaW4gb3VyIHVuaXZhcmlhdGUgRURBIGNvdWxkIHN1Z2dlc3QgYXMgd2VsbC4KCmBgYHtyIGNvci1tYXR9CmNvcl9tYXRyaXggPC0gY29yKGRmWywgY29udF9mZWF0c10pCmhlYXRtYXAoY29yX21hdHJpeCwgbWFpbj0iQ29ycmVsYXRpb24gTWF0cml4IChDbHVzdGVyZWQpIikKY29yX3dpdGhfdGFyZ2V0IDwtIHJvd25hbWVzX3RvX2NvbHVtbihkYXRhLmZyYW1lKGNvcihkZlssIGMoY29udF9mZWF0cyldLCBhcy5udW1lcmljKGRmJHRhcmdldCkpKSkKbmFtZXMoY29yX3dpdGhfdGFyZ2V0KSA8LSBjKCJmZWF0dXJlIiwgInBlYXJzb25fY29yciIpCmNvcl93aXRoX3RhcmdldCAlPiUKICBnZ3Bsb3QoYWVzKHg9cmVvcmRlcihmZWF0dXJlLCAtcGVhcnNvbl9jb3JyKSwgeSA9IHBlYXJzb25fY29ycikpICsgCiAgZ2VvbV9iYXIoc3RhdD0naWRlbnRpdHknKSArIGNvb3JkX2ZsaXAoKSArIGdndGl0bGUoIlBlYXJzb24gQ29ycmVsYXRpb24gb2YgQ29udGludW91cyB3aXRoIFRhcmdldCIpCmBgYAoKCldlIGNhbiB1c2UgUHJpbmNpcGFsIENvbXBvbmVudHMgQW5hbHlzaXMgKFBDQSkgYXMgYSBtZWFucyB0byB2aXN1YWxpc2UgdGhlIGRhdGEgaW4gbG93LWRpbWVuc2lvbiwgdG8gZGV0ZXJtaW5lIGlmIHRoZXJlIGFyZSBhbnkgZXhwbGljaXRseSBkaXNjZXJuaWJsZSB0cmVuZHMuIFdlIGFwcGx5IFBDQSB0byBhbGwgdGhlIGNvbnRpbnVvdXMgZmVhdHVyZXMsIGFuZCBubyBmdXJ0aGVyIHByZS1zY2FsaW5nIGlzIHJlcXVpcmVkIGdpdmVuIHRoZSBjb250aW51b3VzIGZlYXR1cmVzIGhhdmUgdmFsdWVzIGZyb20gJFswLCAxXSQuICBCeSBleWUsIHRoZXJlIGRvIG5vdCBhcHBlYXIgdG8gYmUgYW55IHNpZ25pZmljYW50IGRpZmZlcmVuY2UgaW4gdGhlIFBDQSByZXByZXNlbnRhdGlvbnMgZm9yIGVhY2ggY2xhc3MsIGFsdGhvdWdoIHRoZXJlIGFyZSBtYW55IG9ic2VydmF0aW9ucyB3aXRoIGB0YXJnZXQgPT0gMWAgY2xvc2VyIHRvIHRoZSBib3R0b20gb2YgdGhlIGVsbGlwc29pZCBmb3JtZWQgYnkgdGhlIGZpcnN0IHR3byBQQ0EgbG9hZGluZ3MuIEF0IGxlYXN0IGluIHRoZSBzcGFjZSBmb3JtZWQgYnkgdGhlIGZpcnN0IHR3byBwcmluY2lhbCBjb21wb25lbnRzLCB0aGUgY2xhc3NlcyBkbyBub3QgYXBwZWFyIHRvIGJlIGxpbmVhcmx5IHNlcGFyYWJsZSwgIC0gd2hpY2ggc3VnZ2VzdCBhIG5vbi1saW5lYXIgbWV0aG9kIG1heSBiZSBtb3JlIGVmZmVjdGl2ZSBvbiB0aGlzIGNsYXNzaWZpY2F0aW9uIHRhc2suIE9uIGV4YW1pbmF0aW9uIG9mIHRoZSAqZXhwbGFpbmVkIHZhcmlhbmNlIHJhdGlvKiwgcGxvdHRpbmcgdGhlIHZhcmlhdGlvbiBpbiAkXG1hdGhiZntYfSQgYWdhaW5zdCB0aGUgbnVtYmVyIG9mIHByaW5jaXBhbCBjb21wb25lbnRzLCB3ZSBmaW5kIHRoYXQgdGhlICBmaXJzdCB0d28gcHJpbmNpcGFsIGNvbXBvbmVudHMgb25seSBjYXB0dXJlIGFib3V0ICRcYXBwcm94IDYwXCUkIHZhcmlhdGlvbiBpbiB0aGUgKmNvbnRpbnVvdXMgdmFyaWFibGVzKi4gVG8gY2FwdHVyZSAkXGFwcHJveCA5MFwlJCBvZiB0aGUgdmFyaWF0aW9uLCB3ZSB3b3VsZCBuZWVkIDYgb2YgdGhlIGNvbnRpbnVvdXMgZmVhdHVyZXMsIGFuZCBmb3IgJFxhcHByb3ggOTVcJSB3ZSB3b3VsZCBuZWVkIDkuIFRoaXMgY291bGQgc3VnZ2VzdCB0aGF0IGluY2x1ZGluZyBtb3JlIGZlYXR1cmVzIGNvdWxkIGJlIGJlbmVmaWNpYWwsIHdoaWNoIHdvdWxkIGJlIGEgY29uY2VybiBpZiB3ZSBhcmUgdG8gZG8gICpmZWF0dXJlIHNlbGVjdGlvbiouCgpgYGB7ciBwY2Etdml6fQpwY3MgPC0gcHJjb21wKGRmWyxjb250X2ZlYXRzXSkKc2V0LnNlZWQoMjAyMSkKZGF0YS5mcmFtZShwYzE9cGNzJHhbLDFdLCBwYzI9cGNzJHhbLDJdLCB0YXJnZXQ9ZGZbLCAidGFyZ2V0Il0pICU+JQpnZ3Bsb3QoYWVzKHggPSBwYzEsIHkgPSBwYzIsIGNvbG91ciA9IHRhcmdldCkpICsgCiAgZ2VvbV9qaXR0ZXIoYWxwaGE9MC43KSArIGdndGl0bGUoJ1ByaW5jaXBhbCBDb21wb25lbnRzJykKIyBjdW11bGF0aXZlIHZhcmlhbmNlCmN1bXVsX3ZhciA8LSBjdW1zdW0ocGNzJHNkZXZeMiAvIHN1bShwY3Mkc2Rldl4yKSkKZ2dwbG90KGRhdGEuZnJhbWUoZmVhdHVyZSA9IDE6MTEsIGN1bXVsX3ZhciA9IGN1bXVsX3ZhcikpICsgCiAgZ2VvbV9saW5lKGFlcyh4ID0gZmVhdHVyZSx5ID0gY3VtdWxfdmFyKSkgKyBnZ3RpdGxlKCJDdW11bGF0aXZlIEV4cGxhaW5lZCBWYXJpYW5jZSBSYXRpbyIpICsKICBzY2FsZV95X2NvbnRpbnVvdXMobGFiZWxzPXBlcmNlbnQpICsgeGxhYigiTnVtYmVyIG9mIFByaW5jaXBhbCBDb21wb25lbnRzIikgKyAKICB5bGFiKCJDdW11bGF0aXZlIGV4cGxhaW5lZCBWYXJpYW5jZSBSYXRpbyIpCmBgYAoKIyMgTW9kZWxsaW5nCgpXZSBmaXJzdCBjb25zaWRlciBhIG5haXZlIG1vZGVsIHRoYXQgYWx3YXlzIHByZWRpY3RzIGEgc2luZ2xlIGxhYmVsIChpbiB0aGlzIGNhc2UgJDAkKSBnaXZlbiBpdCBpcyB0aGUgbW9zdCBmcmVxdWVudGx5IG9jY3VycmluZyBjbGFzcy4gSW4gdGhpcyBjYXNlLCB0aGUgYWNjdXJhY3kgd291bGQgICQxIC0gXGhhdHt5fSA9IDAuNzQ1JCBUaGlzIGlsbHVzdHJhdGVzIGEgcG90ZW50aWFsIGlzc3VlIHdpdGggdGhlIGFjY3VyYWN5IG1ldHJpYyAtIHRoZSAqbmFpdmUqIGFjY3VyYWN5IGlzIGhpZ2ggZHVlIHRvIHRoZSBuYXR1cmUgb2YgdGhlIGRhdGEsIGFuZCBoZW5jZSBzdWJzZXF1ZW50IG1vZGVsIHBlcmZvcm1hbmNlcyBuZWVkIHRvIGJlIGNvbXBhcmVkIHdpdGggdGhpcyBiZW5jaG1hcmsuCgpXZSBhbHNvIGNvbnNpZGVyIHRoZSAqKlJPQy1BVUMgbWV0cmljKiogKFJlY2VpdmluZyBPcGVyYXRvciBDaGFyYWN0ZXJpc3RpYyBBcmVhIFVuZGVyIHRoZSBDdXJ2ZSksIGFuZCAqKmFjY3VyYWN5KiogbWV0cmljLiBHaXZlbiB0aGUgcHJvYmxlbSBpcyBvbmUgcmVsYXRlZCB0byBpbnN1cmFuY2UsIHRoZSBtb2RlbGxpbmcgb3V0Y29tZSBvZiBpbnRlcmVzdCBpcyBub3Qgb25seSB0byBvYnRhaW4gdGhlIGNvcnJlY3QgcHJlZGljdGlvbnMgKGFjY3VyYWN5KSwgYnV0IGFsc28gYWNjdXJhdGUgcHJvYmFiaWxpdGllcywgd2hpY2ggaXMgd2hhdCB0aGUgQVVDIG1ldHJpYyBtZWFzdXJlcy4gVGhlIEFVQyBtZXRyaWMgY2FsY3VsYXRlcyB0aGUgYXJlYSB1bmRlciB0aGUgUk9DLWN1cnZlLCB0aGUgcGxvdCBvZiB0aGUgdHJ1ZSBwb3NpdGl2ZSByYXRlIG9yICpzZW5zaXRpdml0eSogJFxmcmFje1RQfXtUUCArIEZOfSQgYWdhaW5zdCB0aGUgZmFsc2UgcG9zaXRpdmUgcmF0ZSAkXGZyYWN7Rk59e1ROICsgRlB9JCwgYXNzZXNzaW5nIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgY2xhc3NpZmllcidzIHByZWRpY3RlZCBwcm9iYWJpbGl0aWVzIGFjcm9zcyBhbGwgcG9zc2libGUgZGVjaXNpb24gdGhyZXNob2xkcy4gQSBjbGFzc2lmaWVyIHRoYXQgYWx3YXlzIHByZWRpY3RzIDBzIHdvdWxkIHJlc3VsdCBpbiBhIGJhc2VsaW5lIEFVQyBvZiAkMC41JC4KCkFzIHdlIGRvIG5vdCBrbm93IHRoZSBzcGVjaWZpYyB0aHJlc2hvbGQgcmVsZXZhbnQgdG8gdGhlIGluc3VyYW5jZSBjb250ZXh0IG9mIHRoZSBwcm9ibGVtLCB3ZSB3aWxsIHJlcG9ydCBib3RoIGFjY3VyYWN5LCB3aXRoIGEgZGVjaXNpb24gdGhyZXNob2xkIHNldCB0byAkPiAwLjUkLCBhbmQgdGhlIEFVQyBzY29yZSBmb3IgYWxsIG1vZGVscyBjb25zaWRlcmVkLiBJbiBwcmFjdGljZSwgdGhlIGRlY2lzaW9uIHRocmVzaG9sZCB3b3VsZCBsYXJnZWx5IGRlcGVuZCBvbiB0aGUgb2JqZWN0aXZlIG9mIHRoZSBtb2RlbGxlci4KCiAKCmBgYHtyfQojIHRyYWluLXRlc3QKWF90cmFpbiA9IGFzLm1hdHJpeChkZl90cmFpblssIGNvbnRfZmVhdHNdKQp5X3RyYWluID0gYXMubnVtZXJpYyhhcy5tYXRyaXgoZGZfdHJhaW4kdGFyZ2V0KSkKWF90ZXN0ID0gYXMubWF0cml4KGRmX3Rlc3RbLCBjb250X2ZlYXRzXSkKeV90ZXN0ID0gYXMubnVtZXJpYyhhcy5tYXRyaXgoZGZfdGVzdCR0YXJnZXQpKQoKZGlhZ25vc2lzIDwtIGZ1bmN0aW9uKHRyYWluX3ByZWQsIHRlc3RfcHJlZCwgdHJhaW5fdHJ1ZSwgdGVzdF90cnVlKXsKICB0cmFpbl9jbGFzc2VzIDwtIGlmZWxzZSh0cmFpbl9wcmVkID4gMC41LCAxLDApCiAgdGVzdF9jbGFzc2VzIDwtIGlmZWxzZSh0ZXN0X3ByZWQgPiAwLjUsIDEsMCkKICBhY2MxIDwtIG1lYW4odHJhaW5fY2xhc3NlcyA9PSB0cmFpbl90cnVlKQogIGF1YzEgPC0gYXVjKHJvYyh0cmFpbl90cnVlLCB0cmFpbl9wcmVkLCBxdWlldD1UUlVFKSkKICBhY2MyIDwtIG1lYW4odGVzdF9jbGFzc2VzID09IHRlc3RfdHJ1ZSkKICBhdWMyIDwtIGF1Yyhyb2ModGVzdF90cnVlLCB0ZXN0X3ByZWQsIHF1aWV0PVRSVUUpKQogIGRhdGEuZnJhbWUodHJhaW5fYWNjPWFjYzEsIHRyYWluX2F1Yz1hdWMxLCB0ZXN0X2FjYyA9IGFjYzIsIHRlc3RfYXVjPWF1YzIpCn0KCgpyZXN1bHRzID0gZGF0YS5mcmFtZShkaWFnbm9zaXMocmVwKDAsIGRpbShkZl90cmFpbilbMV0pLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlcCgwLCBkaW0oZGZfdGVzdClbMV0pLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpLAogICAgICAgICAgICAgICAgICAgICByb3cubmFtZXM9YygibmFpdmUiKSkKcmVzdWx0cwpgYGAKCiMjIyBMb2dpc3RpYyBSZWdyZXNzaW9uIChTR0QpCgpUbyBmdWxmaWxsIHRoZSBwcm9qZWN0IHJlcXVpcmVtZW50cywgd2UgZGVtb25zdHJhdGUgYSBgZnJvbSBzY3JhdGNoJyBTdG9jaGFzdGljIEdyYWRpZW50IERlc2NlbnQgcm91dGluZSAgZm9yIExvZ2lzdGljIFJlZ3Jlc3Npb24uIFRoZSBkZXJpdmF0aW9uIGZvbGxvd3MgW0BoYXN0aWUyMDA5ZWxlbWVudHMsIHBwLiAxMjAtMTI2XQoKQ29uc2lkZXIgYSBtYXRyaXggb2YgdmFyaWFibGVzICRYID0gKHhfezF9LCB4X3syfSwgXGxkb3RzIHhfe259KV57VH0kLCB3aGVyZSAkeF97aX0kIGRlbm90ZSB0aGUgaS10aCByb3cgb3Igb2JzZXJ2YXRpb24sIHRoZSB0YXJnZXQgJFxtYXRoYmZ7eX0gPSAoeV97MX0sIHlfezJ9LCBcbGRvdHMsIHlfe259KSQuIExldCAkcCh4X3tpfTsgXGJldGEpID0gZXhwKFxiZXRhXntUfSB4X3tpfSkkIAoKV2UgYXJlIGludGVyZXN0ZWQgaW4gZmluZGluZyB0aGUgY29lZmZpY2llbnRzICRcYmV0YSQsIHN1Y2ggdGhhdCB0aGUgKipsb2dpc3RpYyBsb3NzKiogb3IgbmVnYXRpdmUgbG9nLWxpa2VsaWhvb2QgaXMgbWluaW1pc2VkLiBUaGUgbG9naXN0aWMgbG9zcyBpcyBnaXZlbiBieToKCiQkClxiZWdpbnthbGlnbn1sKFxib2xkc3ltYm9se1xiZXRhfSkgJj0gLVxzdW1fe2kgPSAxfV57Tn0geV97aX0gbG9nKHAoeF97aX0gOyBcYm9sZHN5bWJvbHtcYmV0YX0pKSArICgxIC0geV97aX0pIGxvZygxIC0gcCh4X3tpfSA7IFxib2xkc3ltYm9se1xiZXRhfSkpXFwgCiY9IFxzdW1fe2kgPSAxfV57Tn0gXGxlZnQgWyB5X3tpfWxvZyBcbGVmdCAoXGZyYWN7cCh4X3tpfSA7IFxib2xkc3ltYm9se1xiZXRhfSl9ezEgLSBwKHhfe2l9IDsgXGJvbGRzeW1ib2x7XGJldGF9KX0gXHJpZ2h0KSArIGxvZygxIC0gcCh4X3tpfSA7IFxib2xkc3ltYm9se1xiZXRhfSkpIFxyaWdodCBdXFwKIGwoXGJvbGRzeW1ib2x7XGJldGF9KSAmPSAtXHN1bV97aSA9IDF9XntOfVxsZWZ0IFt5X3tpfSBcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IHhfe2l9IC0gbG9nKDEgKyBleHAoeF97aX1cYm9sZHN5bWJvbHtcYmV0YX0pKSBccmlnaHQgXQpcZW5ke2FsaWdufQokJAoKCldpdGggdGhlIGluY2x1c2lvbiBvZiBhIHJlZ3VsYXJpc2F0aW9uIHRlcm0sIGluIHRoaXMgY2FzZSBhICRMXnsyfSQgcGVuYWx0eSwgdGhlIGxvc3MgZnVuY3Rpb24gYmVjb21lczoKCiQkIGwoXGJvbGRzeW1ib2x7XGJldGF9KSA9IC1cc3VtX3tpID0gMX1ee059IFxsZWZ0IFt5X3tpfSBcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IHhfe2l9IC0gbG9nKDEgKyBleHAoXGJvbGRzeW1ib2x7XGJldGF9XntUfXhfe2l9KSkgXHJpZ2h0IF0gLSBcbGFtYmRhIFxib2xkc3ltYm9se1xiZXRhfV57VH0gXGJvbGRzeW1ib2x7XGJldGF9JCQKClRoZSBncmFkaWVudCBvZiB0aGUgbG9zcyBmdW5jdGlvbiB3aXRoIHJlc3BlY3QgdG8gdGhlIGNvZWZmaWNpZW50cyAkXG1hdGhiZntcYmV0YX0kIGlzIGdpdmVuIGJ5OgoKJCRcbmFibGEoXGJvbGRzeW1ib2x7XGJldGF9KSA9IC1cc3VtX3tpID0gMX1ee059IFxsZWZ0IFsgeV97aX0geF97aX0gLSBcZnJhY3t4X3tpfWV4cChcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IHhfe2l9KX17MSArIGV4cChcYm9sZHN5bWJvbHtcYmV0YX1ee1R9IHhfe2l9KX0gXHJpZ2h0XSAtIFxsYW1iZGEgMlxib2xkc3ltYm9se1xiZXRhfSQkCgpXZSBhcHBseSBzdG9jaGFzdGljIGdyYWRpZW50IGRlc2NlbnQuIEluIHNob3J0LCB0aGlzIHJlbGllcyBvbiB1cGRhdGluZyB0aGUgY29lZmZpY2llbnRzICRcYmV0YSQgaXRlcmF0aXZlbHkgYmFzZWQgb24gYSBzdGVwIHNpemUgJFxsYW1iZGEkOgoKJFxiZXRhX3t0ICsgMX0gPSBcYmV0YV97dH0gLSBcbGFtYmRhIFxuYWJsYShcYm9sZHN5bWJvbHtcYmV0YX1fe3R9KSQKCldlIHVzZSB0aGUgQmFyemlsYWktQm9yd2VpbiBtZXRob2QgW0BtdXJwaHkyMDEybWFjaGluZSwgcHAuIDQ0NC00NDVdIHRvIGRldGVybWluZSB0aGUgc3RlcCBzaXplLgoKJFxsYW1iZGFfe3R9ID0gXGZyYWN7fChcYmV0YV97dH0gLSBcYmV0YV97dCAtIDF9KV57VH0oXG5hYmxhIEYoXGJldGFfe3R9KSAtICBcbmFibGEgRihcYmV0YV97dCAtIDF9KSl8fXtcfCBcbmFibGEgRihcYmV0YV97dH0pIC0gIFxuYWJsYSBGKFxiZXRhX3t0IC0gMX0pKVx8XnsyfX0kCgpgYGB7ciBncmFkaWVudC1kZXNjZW50fQojIGJpbmFyeSBjcm9zc2VudHJvcHkgLyBsb2ctbG9zcwpsb2dfbG9zcyA8LSBmdW5jdGlvbih4LCB5LCBiZXRhcywgbGFtYmRhKXsKICBsb2dpdHMgPC0geCAlKiUgYmV0YXMKICAtICh0KHkpICUqJSBsb2dpdHMgLSBzdW0obG9nKDEgKyBleHAobG9naXRzKSkpICsgbGFtYmRhICogdChiZXRhcykgJSolIGJldGFzKSAvIGRpbSh4KVsxXQp9CiMgbG9naXN0aWMgcmVncmVzc2lvbiBncmFkaWVudHMKZ3JhZGllbnRzIDwtIGZ1bmN0aW9uKHgsIHksIGJldGFzLCBsYW1iZGEpewogIGxvZ2l0cyA8LSB4ICUqJSBiZXRhcwogIC0gKHQoeCkgJSolICh5IC0gZXhwKGxvZ2l0cykvKDEgKyBleHAobG9naXRzKSkpKSAtIGxhbWJkYSAqMiAqIGJldGFzIC8gZGltKHgpWzFdCn0KcCA9IGRpbShYX3RyYWluKVsyXQpsYW1iZGEgPSAwCm5faXRlcnMgPC0gMTAwCmluaXRfc3RlcF9zaXplIDwtIDFlLTYKc2V0LnNlZWQoMjAyMSkKYmV0YV9pbml0IDwtIG1hdHJpeChybm9ybShwKSxucm93PXApCmJldGFfcGF0aCA8LSBtYXRyaXgocmVwKDAsIG5faXRlcnMgKiBwKSwgbnJvdyA9IG5faXRlcnMsIG5jb2w9cCkKYmV0YV9wYXRoWzEsXSA9IGJldGFfaW5pdApsYXN0X2dyYWQgPC0gZ3JhZCA8LSBncmFkaWVudHMoWF90cmFpbiwgeV90cmFpbiwgYmV0YV9wYXRoWzEsXSwgbGFtYmRhKQpiZXRhX3BhdGhbMixdID0gYmV0YV9pbml0IC0gaW5pdF9zdGVwX3NpemUgKiBncmFkCmdyYWQgPC0gZ3JhZGllbnRzKFhfdHJhaW4sIHlfdHJhaW4sIGJldGFfcGF0aFsyLF0sIGxhbWJkYSkKbG9zc2VzIDwtIHJlcCgwLCBuX2l0ZXJzKQpmb3IgKGkgaW4gMzpuX2l0ZXJzKXsKICAgIHN0ZXBfc2l6ZSA8LSBhcy5udW1lcmljKHQoYmV0YV9wYXRoW2kgLSAxLF0gLSBiZXRhX3BhdGhbaSAtIDIsXSkgJSolIChncmFkIC0gbGFzdF9ncmFkKSAvIAogICAgICAgICAgICAgICAgICAgICh0KGdyYWQgLSBsYXN0X2dyYWQpICUqJSAoZ3JhZCAtIGxhc3RfZ3JhZCkpKQogICAgYmV0YV9wYXRoW2ksXSA8LSBiZXRhX3BhdGhbaSAtIDEsXSAtIHN0ZXBfc2l6ZSAqIGdyYWQKICAgIGxhc3RfZ3JhZCA8LSBncmFkCiAgICBncmFkIDwtIGdyYWRpZW50cyhYX3RyYWluLCB5X3RyYWluLCBiZXRhX3BhdGhbaSwgXSwgbGFtYmRhKQogICAgbG9zc2VzW2ldIDwtIGxvZ19sb3NzKFhfdHJhaW4sIHlfdHJhaW4sIGJldGFfcGF0aFtpLF0sIGxhbWJkYSkKfQpnZ3Bsb3QoZGF0YS5mcmFtZShzdGVwID0gMzpuX2l0ZXJzLCBsb3NzPWxvc3Nlc1szOm5faXRlcnNdKSkgKyAKICBnZW9tX2xpbmUoYWVzKHggPSBzdGVwLCB5ID0gbG9zcykpICsKICBnZ3RpdGxlKCJCaW5hcnkgQ3Jvc3NlbnRyb3B5IHZzLiBJdGVyYXRpb25zIikKCnByZWRfdHJhaW4gPC0gYXMubnVtZXJpYygxIC8gKDEgKyBleHAoLVhfdHJhaW4gJSolIGJldGFfcGF0aFsxMDAsXSkpKQpwcmVkX3Rlc3QgPC0gYXMubnVtZXJpYygxIC8gKDEgKyBleHAoLVhfdGVzdCAlKiUgYmV0YV9wYXRoWzEwMCxdKSkpCnJlc3VsdHNbInNnZCIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJzZ2QiLF0KYGBgCgpXZSBhcHBseSBvdXIgImZyb20gc2NyYXRjaCIgaW1wbGVtZW50YXRvbiBvZiBTR0QgTG9naXN0aWMgUmVncmVzc2lvbiB1c2luZyBhbGwgdGhlIG51bWVyaWNhbCB2YXJpYWJsZXMsIG9idGFpbmluZyBhIHRlc3QgYWNjdXJhY3kgb2YgJDAuNzUxJCBhbmQgYSB0ZXN0IEFVQyBvZiAkMC43MDgyJC4gR2l2ZW4gdGhlIGxpbWl0YXRpb25zIG9mIG91ciBpbXBsZW1lbnRhdGlvbiwgZm9yIGV4YW1wbGUgYW4gaW5hYmlsaXR5IHRvIHByb2Nlc3MgdGhlICpmYWN0b3IqIGRhdGF0eXBlICh1bmxlc3Mgd2UgYXBwZW5kIGEgb25lLWhvdCBlbmNvZGVkIG1hdHJpeCksIHdlIHNoYWxsIHN1YnNlcXVlbnRseSB1c2UgdGhlIGBnbG1gIHBhY2thZ2UgZm9yIGxvZ2lzdGljIHJlZ3Jlc3Npb24sIGFuZCB0aGUgYGdsbW5ldGAgcGFja2FnZSBmb3IgcmVndWxhcmlzZWQgbG9naXN0aWMgcmVncmVzc2lvbi4KCiMjIyBMb2dpc3RpYyBSZWdyZXNzaW9uIChGZXcgUHJlZGljdG9ycykKCkhhdmluZyBpbnRyb2R1Y2VkIGxvZ2lzdGljIHJlZ3Jlc3Npb24gaW4gdGhlIHByZXZpb3VzIG1vZGVsLCB3ZSBzZWVrIHRvIGJ1aWxkIGEgc2ltcGxlciBtb2RlbCB3aXRoIGJldHRlciBpbnRlcnByZXRhYmlsaXR5IHRvIGNvbXBhcmUgdGhlIHBlcmZvcm1hbmNlIG9mIGFsbCBvdGhlciBtb2RlbHMgdG8uIEluIHRoaXMgc2VjdGlvbiwgd2UgYnVpbGQgYSBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsIHdpdGggYSBmZXcgcHJlZGljdG9ycywgd2hpY2ggYXJlIHNlbGVjdGVkIGZyb20gb3VyIGV4cGxvcmF0b3J5IGRhdGEgYW5hbHlzaXMgdG8gaGF2ZSBkaXNjZXJuaWJsZSBkaWZmZXJlbmNlcyBpbiB0YXJnZXQuIFRoZXNlIGFyZSBgY29udDMsIGNvbnQ0LCBjYXQxMywgY2F0MThgLiBXZSB3aWxsIHJlZmVyIHRvIHRoaXMgbW9kZWwgYXMgb3VyICoqYmFzZWxpbmUgbW9kZWwqKi4gCgpgYGB7ciBnbG0tYmFzZWxpbmV9CmdsbTEgPC0gZ2xtKHRhcmdldH5jb250Mytjb250NCtjYXQxMytjYXQxOCxkYXRhPWRmX3RyYWluLCBmYW1pbHk9Ymlub21pYWwobGluaz0ibG9naXQiKSkKc3VtbWFyeShnbG0xKQp2aWYoZ2xtMSkKZ2djb2VmKGdsbTEpCmBgYAoKVGhlIGdlbmVyYWxpc2VkIHZhcmlhbmNlIGluZmxhdGlvbiBmYWN0b3IgKEdWSUYpIHRlbGxzIHVzIHRoZSBleHRlbnQgdG8gd2hpY2ggdGhlIHN0YW5kYXJkIGVycm9yIG9mIGEgcHJlZGljdG9yIGlzIGluY3JlYXNlZCBkdWUgdG8gaXRzIGNvcnJlbGF0aW9uIHdpdGggb3RoZXIgcHJlZGljdG9ycyBpbiB0aGUgbW9kZWwsIGNvcnJlY3RlZCBieSB0aGUgbnVtYmVyIG9mIGRlZ3JlZXMgb2YgZnJlZWRvbSBjb3JyZXNwb25kaW5nIHRvIHRoZSBudW1iZXIgb2YgbGV2ZWxzIGluIHRoZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMuIFRoZSBHVklGIG9mIGFsbCBwcmVkaWN0b3JzIGluIG91ciBtb2RlbCBhcmUgbGVzcyB0aGFuIDIsIHdoaWNoIHNob3dzIG5vIGV2aWRlbmNlIG9mIG11bHRpY29sbGluZWFyaXR5LiBBbGwgZm91ciBwcmVkaWN0b3JzIGFyZSBzaWduaWZpY2FudCBhdCA1JSBsZXZlbCwgd2l0aCB0aGUgbW9zdCBzaWduaWZpY2FudCBwcmVkaWN0b3IgYmVpbmcgY2F0MTMsIHdoaWNoIGhhcyBhIHAtdmFsdWUgb2YgbGVzcyB0aGFuIDElLiBUaGUgY29lZmZpY2llbnRzIG9mIHRoZSBwcmVkaWN0b3JzIHJlcHJlc2VudCB0aGUgYXNzb2NpYXRpb24gb2YgdGhhdCBwcmVkaWN0b3Igd2l0aCB0aGUgbG9nIG9kZHMgb2YgdGFyZ2V0LCB3aGljaCBpcyBkZWZpbmVkIGFzICQkbG9nIFAodGFyZ2V0PTEpL1AodGFyZ2V0PTApJCQKClRoZSBjb2VmZmljaWVudHMgb2YgdGhlIGR1bW15IHZhcmlhYmxlcyBpbmRpY2F0ZSB0aGUgYXZlcmFnZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGxvZyBvZGRzIG9mIHRoYXQgZmFjdG9yIGxldmVsIGdyb3VwIGNvbXBhcmVkIHRvIHRoZSBiYXNlbGluZSBsZXZlbCBncm91cC4gSW4gb3VyIHJlZ3Jlc3Npb24sIHRoZSBmaXJzdCBjYXRlZ29yeSAoQSkgb2YgZWFjaCBjYXRlZ29yaWNhbCB2YXJpYWJsZSBpcyB0YWtlbiBhcyB0aGUgYmFzZWxpbmUgZ3JvdXAuIEZvciBleGFtcGxlLCB0aGUgY29lZmZpY2llbnQgb2Yg4oCYY2F0MTNC4oCZIGltcGxpZXMgdGhlIGZvbGxvd2luZyBlcXVhdGlvbjogCiQkXGxvZ1xmcmFje1AodGFyZ2V0PTF8Y2F0MTM9Qil9e1AodGFyZ2V0PTB8Y2F0MTM9Qil9LVxsb2dcZnJhY3tQKHRhcmdldD0xfGNhdDEzPUEpfXtQKHRhcmdldD0wfGNhdDEzPUEpfT0xLjg2ODEkJApUaGlzIG1lYW5zIHRoYXQgY2xhaW1zIHdpdGgg4oCYY2F0MTM9QuKAmSBoYXZlIGV4cCgxLjg2ODEpLTE9NS40OCBoaWdoZXIgb2RkcyB0aGFuIGNsYWltcyB3aXRoIOKAmGNhdDEzPUHigJkuIFRoZSBjb2VmZmljaWVudCBvZiBjYXQxOEIgaXMgbm90IHNpZ25pZmljYW50LCB3aGljaCBpbXBsaWVzIHRoYXQgaXRzIGFzc29jaWF0aW9uIHdpdGggdGFyZ2V0IGlzIG5vdCBzaWduaWZpY2FudGx5IGRpZmZlcmVudCBmcm9tIOKAmGNhdDE4PUHigJkuIEhvd2V2ZXIsIGhhdmluZyDigJhjYXQxOD1D4oCZIG1ha2VzIHRoZSBjbGFpbSBleHAoMi42MDgxKS0xPTEyLjYgdGltZXMgbW9yZSBsaWtlbHkgdG8gaGF2ZSDigJh0YXJnZXQ9PTHigJkgdGhhbiBoYXZpbmcg4oCYY2F0MTg9QeKAmS4gU2ltaWxhcmx5LCBjbGFpbXMgd2l0aCDigJhjYXQxOD1E4oCZIGFyZSBleHAoMi40MzQyKS0xPTkuNCB0aW1lcyBtb3JlIGxpa2VseSB0byBoYXZlIOKAmHRhcmdldD09MeKAmSB0aGFuIGNsYWltcyB3aXRoIOKAmGNhdDE4PUHigJkuCgpUbyBpbnRlcnByZXQgdGhlIGNvZWZmaWNpZW50cyBvZiB0aGUgY29udGludW91cyB2YXJpYWJsZXMsIGxvZyBvZGRzIG5lZWQgdG8gYmUgY2FsY3VsYXRlZCB1c2luZyBzcGVjaWZpYyBwYWlycyBvZiB2YWx1ZXMgb2YgdGhlIHByZWRpY3RvcnMuIFRoZSBub24tbGluZWFyaXR5IG9mIHRoZSBsb2dpc3RpYyBmdW5jdGlvbiBtZWFucyB0aGF0IGEgY2hhbmdlIG9mIG9uZSB1bml0IGluIHRoZSB2YWx1ZSBvZiBhIHByZWRpY3RvciBpcyBub3QgdGhlIHNhbWUgYWNyb3NzIHRoZSByYW5nZSBvZiB0aGUgcHJlZGljdG9yLiDigJhjb250M+KAmSBhbmQg4oCYY29udDTigJkgaGF2ZSBuZWdhdGl2ZSBjb2VmZmljaWVudHMgYXMgZXhwZWN0ZWQsIGFuZCBhcmUgaW50ZXJwcmV0ZWQgYXMgZm9sbG93cy4gQSBvbmUgdW5pdCBpbmNyZWFzZSBpbiDigJhjb250M+KAmSBpcyBhc3NvY2lhdGVkIHdpdGggYW4gZXhwKC0wLjY1NTQpPTAuNTE5IG11bHRpcGxpY2F0aXZlIGVmZmVjdCBvbiB0aGUgb2RkcywgaS5lLiBhIDQ4JSBkZWNyZWFzZSBpbiBvZGRzIGNvbXBhcmVkIHRvIHRoZSBwcmV2aW91cyBvZGRzLiBTaW1pbGFybHksIGEgY2xhaW0gd2l0aCBhIG9uZSB1bml0IGhpZ2hlciB2YWx1ZSBvZiDigJhjb250NOKAmSBpcyAxLWV4cCgtMC40NzcyKT0zNy45JSBsZXNzIGxpa2VseSB0byBoYXZlIOKAmHRhcmdldD09MeKAmSB0aGFuIGEgY2xhaW0gd2l0aCBhIG9uZSB1bml0IGxvd2VyIHZhbHVlIG9mIOKAmGNvbnQ04oCZLiBXZSBub3RlIHRoYXQgYXMgYWxsIGNvbnRpbnVvdXMgdmFyaWFibGVzIGluIHRoaXMgZGF0YXNldCBhcmUgbm9ybWFsaXNlZCwgaW5jcmVhc2luZyBhIHZhcmlhYmxlIGJ5IG9uZSB1bml0IGltcGxpZXMgaW5jcmVhc2luZyBpdCBieSBvbmUgc3RhbmRhcmQgZGV2aWF0aW9uIGhpZ2hlciB0aGFuIHRoZSBtZWFuIGluIGl0cyBvcmlnaW5hbCB1bml0cy4gCgoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KcHJlZF90cmFpbiA8LSBwcmVkaWN0KGdsbTEsIGRmX3RyYWluLCB0eXBlPSJyZXNwb25zZSIpCnByZWRfdGVzdCA8LSBwcmVkaWN0KGdsbTEsIGRmX3Rlc3QsIHR5cGU9InJlc3BvbnNlIikKcmVzdWx0c1siZ2xtLXNtYWxsIixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbImdsbS1zbWFsbCIsXQpgYGAKCiMjIyBMb2dpc3RpYyBSZWdyZXNzaW9uIChBbGwgUHJlZGljdG9ycykKCldlIG5vdyBydW4gYSBsb2dpc3RpYyByZWdyZXNzaW9uIHVzaW5nIGFsbCAzMSBwcmVkaWN0b3JzIChmdWxsIG1vZGVsKS4gVGhlIHJlZ3Jlc3Npb24gY29lZmZpY2llbnRzIGNhbiBiZSBpbnRlcnByZXRlZCBpbiBhIHNpbWlsYXIgd2F5IGFzIHRoZSBiYXNlbGluZSBtb2RlbC4gVGhlIHJlZ3Jlc3Npb24gb3V0cHV0IHNob3dzIHRoYXQgYWxsIHByZWRpY3RvcnMgYXJlIHNpZ25pZmljYW50IGF0IDUlLCBidXQgdGhpcyBpcyB1bnJlbGlhYmxlIHNpbmNlIHRoZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgaGF2ZSBtYW55IGxldmVscyAoNjIzIGluIHRvdGFsKS4gCgpUaGUgZnVsbCBtb2RlbCBoYXMgYSBoaWdoZXIgdHJhaW4gYWNjdXJhY3kgKDAuODAxKSBidXQgbG93ZXIgdGVzdCBhY2N1cmFjeSAoMC41OSkgdGhhbiB0aGUgYmFzZWxpbmUgbW9kZWwsIHdoaWNoIGltcGxpZXMgb3ZlcmZpdHRpbmcuIFRoZSB0ZXN0IEFVQyBpcyAwLjU0Mywgd2hpY2ggaXMgbXVjaCBsb3dlciB0aGFuIHRoZSBiYXNlbGluZS4gVGhpcyBpcyBhbiBleGFtcGxlIG9mIHRoZSBiaWFzLXZhcmlhbmNlIHRyYWRlLW9mZjsgdGhlIG1vcmUgY29tcGxleCwgZnVsbCBtb2RlbCB3aXRoIDMxIHByZWRpY3RvcnMgaGFzIGEgbG93ZXIgYmlhcyBidXQgaGlnaGVyIHZhcmlhbmNlIHRoYW4gdGhlIHNpbXBsZXIsIGJhc2VsaW5lIG1vZGVsIHdpdGggNCBwcmVkaWN0b3JzLiBXZSBhbHNvIG9idGFpbiBhbiBlcnJvcjog4oCccHJlZGljdGlvbiBmcm9tIGEgcmFuay1kZWZpY2llbnQgZml0IG1heSBiZSBtaXNsZWFkaW5n4oCdIHdoaWNoIHN1Z2dlc3RzIG11bHRpY29sbGluZWFyaXR5LiBJbiBzdWJzZXF1ZW50IHNlY3Rpb25zLCB3ZSBhaW0gdG8gb3ZlcmNvbWUgdGhpcyB0byBpbXByb3ZlIHRoZSBzdGFiaWxpdHkgb2Ygb3VyIG1vZGVsIHVzaW5nIHNocmlua2FnZSBpbiBbc2VjdGlvbiAzYl0uCgpgYGB7ciBnbG0tZnVsbC1yZXN1bHRzLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFLCBvdXRwdXQ9RkFMU0V9CmdsbTIgPC0gZ2xtKHRhcmdldH4uLCBkYXRhPWRmX3RyYWluLCBmYW1pbHk9Ymlub21pYWwobGluaz0ibG9naXQiKSwgCiAgICAgICAgICAgIGNvbnRyb2wgPSBsaXN0KG1heGl0ID0gMTAwKSkKIyBkaXNwbGF5KGdsbTIpCgpwcmVkX3RyYWluIDwtIHByZWRpY3QoZ2xtMiwgZGZfdHJhaW4sIHR5cGU9InJlc3BvbnNlIikKZ2xtMiR4bGV2ZWxzID0gbGFwcGx5KGRmWyxjYXRfZmVhdHNdLCBsZXZlbHMpCnByZWRfdGVzdCA8LSBwcmVkaWN0KGdsbTIsIGRmX3Rlc3QsIHR5cGU9InJlc3BvbnNlIikKcmVzdWx0c1siZ2xtLWZ1bGwiLF0gPC0gZGlhZ25vc2lzKHByZWRfdHJhaW4sIHByZWRfdGVzdCwgZGZfdHJhaW4kdGFyZ2V0LCBkZl90ZXN0JHRhcmdldCkKcmVzdWx0c1siZ2xtLWZ1bGwiLF0KIyBhbm92YShnbG0xLCBnbG0yLCB0ZXN0PSJDaGlzcSIpCmBgYAoKIyMjIE91dGxpZXIgRGV0ZWN0aW9uCkF0IHRoaXMgc3RhZ2UsIHdlIHN1c3BlY3QgdGhhdCBzb21lIG91dGxpZXJzIG1pZ2h0IGJlIGhlYXZpbHkgaW5mbHVlbmNpbmcgdGhlIHBlcmZvcm1hbmNlIG9mIG91ciBtb2RlbHMsIGFuZCBoZW5jZSB3ZSBzZWVrIHRvIGRldGVjdCBvdXRsaWVycyB1c2luZyBhIGZldyBtZWFzdXJlcy4gRm9ybWFsbHksIG91dGxpZXJzIGFyZSBkZWZpbmVkIGFzIG9ic2VydmF0aW9ucyB3aXRoIGEgcmVzcG9uc2UgdmVjdG9yIHRoYXQgaXMgdW51c3VhbCBjb25kaXRpb25hbCBvbiBjb3ZhcmlhdGVzIChwcmVkaWN0b3JzKS4gRmlyc3RseSwgd2UgbG9vayBmb3IgcG9pbnRzIHdpdGggbGFyZ2UgKHN0dWRlbnRpc2VkKSByZXNpZHVhbHMgYW5kIHdlIGNhbiB0ZXN0IGlmIHRoZXNlIHJlc2lkdWFscyBhcmUgc2lnbmlmaWNhbnRseSBsYXJnZXIgdGhhbiB0aG9zZSBvZiBvdGhlciBwb2ludHMgYnkgbG9va2luZyBhdCB0aGUgQm9uZmVycm9uaS1hZGp1c3RlZCBwLXZhbHVlcy4gMTAgcG9pbnRzIGFyZSBpZGVudGlmaWVkIHRvIGhhdmUgbGFyZ2Ugc3R1ZGVudGlzZWQgcmVzaWR1YWxzIHdpdGggYWRqdXN0IHAtdmFsdWVzIGxlc3MgdGhhbiAwLjA1LiBXZSBzdG9yZSB0aGUgaW5kaWNlcyBvZiB0aGVzZSBwb2ludHMgdG8gYmUgcmVtb3ZlZCBsYXRlci4KCmBgYHtyfQpvdXRsaWVyVGVzdChnbG0yKQpvdXRsaWVycyA8LSBhcy5udW1lcmljKG5hbWVzKG91dGxpZXJUZXN0KGdsbTIpJHApKQpgYGAKCk9ic2VydmF0aW9ucyB0aGF0IGFyZSBmYXIgZnJvbSB0aGUgYXZlcmFnZSBjb3ZhcmlhdGUgcGF0dGVybiBhcmUgY29uc2lkZXJlZCB0byBoYXZlIGhpZ2ggbGV2ZXJhZ2UgYW5kIGNhbiBiZSBtZWFzdXJlZCB1c2luZyBoYXQgdmFsdWVzLiBIZXJlLCB0aGVyZSBhcmUgYXQgbGVhc3QgMTAwIHBvaW50cyB3aXRoIGhpZ2ggbGV2ZXJhZ2UuIAoKRmluYWxseSwgd2UgbWVhc3VyZSBmb3IgaW5mbHVlbmNlLCB3aGljaCBpcyBhbiBvYnNlcnZhdGlvbiB0aGF0IGlzIGFuIG91dGxpZXIgYW5kIGhhdmUgaGlnaCBsZXZlcmFnZS4gVGhlc2UgYXJlIGxpa2VseSB0byBpbmZsdWVuY2UgdGhlIHJlZ3Jlc3Npb24gY29lZmZpY2llbnRzIGFuZCBpbmZsdWVuY2UgY2FuIGJlIHRob3VnaHQgb2YgYXMgdGhlIHByb2R1Y3Qgb2YgbGV2ZXJhZ2UgYW5kIG91dGxpZXIuIEhlcmUsIHdlIHBsb3Qgc3R1ZGVudGlzZWQgcmVzaWR1YWxzIGFnYWluc3QgaGF0LXZhbHVlcyB3aXRoIHRoZSBzaXplIG9mIGEgY2lyY2xlIGJlaW5nIHByb3BvcnRpb25hbCB0byB0aGUgQ29vaydzIGRpc3RhbmNlIG9mIGFuIG9ic2VydmF0aW9uLSBhIG1lYXN1cmUgb2YgaW5mbHVlbmNlLgoKCmBgYHtyfQppbmZsdWVuY2VJbmRleFBsb3QoZ2xtMiwgdmFycyA9ICJoYXQiKQpgYGAKCmBgYHtyfQppbmZsdWVuY2VQbG90KGdsbTIpCmBgYAoKV2Ugb2JzZXJ2ZSB0aGF0IHRoZXJlIGFyZSA0IG9ic2VydmF0aW9ucyB3aXRoIGhpZ2ggaW5mbHVlbmNlLiBXZSByZW1vdmUgdGhlc2Ugb2JzZXJ2YXRpb25zIGFsb25nIHdpdGggdGhlIHBvaW50cyBpZGVudGlmaWVkIGFzIG91dGxpZXJzIGVhcmxpZXIgKDE0IGluIHRvdGFsKSwgYW5kIGNvbXBhcmUgdGhlIHBlcmZvcm1hbmNlIG9mIG91ciB1cGRhdGVkIG1vZGVsIHdpdGggdGhlIG9yaWdpbmFsIG1vZGVsLiAKCmBgYHtyIGluZmx1ZW5jZXJzfQppbmZsdWVuY2VycyA8LSBhcy5udW1lcmljKHJvd25hbWVzKGluZmx1ZW5jZVBsb3QoZ2xtMikpKQpnbG0yX2luZmx1ZW5jZXJzIDwtIHVwZGF0ZShnbG0yLCBzdWJzZXQgPSBjKC1pbmZsdWVuY2VycykpCmdsbTJfb3V0bGllcnMgPC0gdXBkYXRlKGdsbTIsIHN1YnNldCA9IGMoLW91dGxpZXJzKSkKcmVtb3ZhbF9saXN0IDwtIHVuaW9uKG91dGxpZXJzLCBpbmZsdWVuY2VycykKZ2xtMl9yZW1vdmVkIDwtIHVwZGF0ZShnbG0yLCBzdWJzZXQgPSBjKC1yZW1vdmFsX2xpc3QpKQpjb21wYXJlQ29lZnMoZ2xtMiwgZ2xtMl9pbmZsdWVuY2VycywgZ2xtMl9vdXRsaWVycywgZ2xtMl9yZW1vdmVkKQojIGFjdHVhbGx5IGp1c3QgdXNlIGdsbTIgYW5kIGdsbTJfcmVtb3ZlZApgYGAKClJlbW92aW5nIG91dGxpZXJzIGxlZCB0byBhIGhpZ2hlciB0ZXN0IGFjY3VyYWN5IG9mIDAuNjg0IGJ1dCBhIGxvd2VyIHRlc3QgQVVDIG9mIDAuNTM5LiBXZSBjYW5ub3QgaW50ZXJwcmV0IHRoaXMgZnVydGhlciB3aXRob3V0IGtub3dpbmcgdGhlIHNwZWNpZmljIHRocmVzaG9sZCB1c2VkIHRvIGNsYXNzaWZ5IHRoZSB0YXJnZXQgaW4gdGhlIGRhdGEuIEFuYWx5c2luZyB0aGUgcmVncmVzc2lvbiBvdXRwdXQsIHdlIHNlZSB0aGF0IGxlYXZpbmcgb3V0IHRoZSBvdXRsaWVycyBkb2VzIG5vdCBjaGFuZ2UgdGhlIGNvZWZmaWNpZW50IGVzdGltYXRlcywgYW5kIHNpbmNlIHdlIGhhdmUgbm8gaW50dWl0aXZlIHJlYXNvbiB0byBiZWxpZXZlIHRoYXQgdGhlc2Ugb3V0bGllciB2YWx1ZXMgYXJlIGV4dHJlbWUgKGR1ZSB0byBubyBrbm93bGVkZ2UgYWJvdXQgdGhlIHZhcmlhYmxlcyB0aGVtc2VsdmVzKSwgd2UgZGVjaWRlZCB0byBrZWVwIHRoZXNlIG91dGxpZXIgZGF0YSBwb2ludHMgZm9yIGFsbCBvdGhlciBtb2RlbHMuCgoKIyMjIFJlZ3VsYXJpc2VkIExvZ2lzdGljIFJlZ3Jlc3Npb24KCkdpdmVuIHRoZSBpc3N1ZSBvZiAqaGlnaCBkaW1lbnNpb25hbGl0eSosIHdlIGNvbnNpZGVyIGEgcmVndWxhcmlzZWQgZm9ybSBvZiBsb2dpc3RpYyByZWdyZXNzaW9uLiBTcGVjaWZpY2FsbHksIHdlIGNvbnNpZGVyIHJpZGdlIChsb2dpc3RpYykgcmVncmVzc2lvbi4gVGhpcyBtZXRob2Qgc2hyaW5rcyBjb2VmZmljaWVudHMgYnkgaW1wb3NpbmcgYSBwZW5hbHR5IG9uIHRoZWlyIHNpemUsIHRoZXJlYnkgcmVkdWNpbmcgbW9kZWwgY29tcGxleGl0eS4gIFdlIHVzZSB0aGUgaW1wbGVtZW50YXRpb24gb2ZmZXJlZCBieSB0aGUgIGBnbG1uZXRgIHBhY2thZ2U7IGluIGRvaW5nIHNvIHdlIG5lZWQgdG8gY29udmVydCB0aGUgZGF0YSB0eXBlIGludG8gbWF0cmljZXMuVGhlIGBnbG1uZXRgIHBhY2thZ2UgcmVxdWlyZXMgdGhlIGRhdGEgdG8gYmUgaW4gYSAqbWF0cml4KiBkYXRhIHR5cGUsIGFuZCBoZW5jZSB3ZSBtYWtlIHRoZSBjb3JyZXNwb25kaW5nIGFkanVzdG1lbnQuCgpgYGB7ciBnbG0tcmlkZ2Utc2NvcmVzLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpYX3RyYWluID0gZGZfdHJhaW5bLCAtbGVuZ3RoKGRmX3RyYWluKV0KeV90cmFpbiA8LSBkZl90cmFpbiR0YXJnZXQKWF90ZXN0ID0gZGZfdGVzdFssIC1sZW5ndGgoZGZfdGVzdCldCnlfdGVzdCA8LSBkZl90ZXN0JHRhcmdldApYX3RyYWluID0gbW9kZWwubWF0cml4KH4uLCBYX3RyYWluKQpYX3Rlc3QgPSBtb2RlbC5tYXRyaXgofi4sIFhfdGVzdCkKZ2xtMyA8LSBjdi5nbG1uZXQoWF90cmFpbiwgeV90cmFpbiwgCiAgICAgICAgICAgICAgICAgIGZhbWlseT0iYmlub21pYWwiKGxpbms9ImxvZ2l0IiksIGFscGhhPTApCmdsbTMKcHJlZF90cmFpbiA8LSBhcy5udW1lcmljKHByZWRpY3QoZ2xtMywgWF90cmFpbiwgdHlwZT0icmVzcG9uc2UiKSkKcHJlZF90ZXN0IDwtIGFzLm51bWVyaWMocHJlZGljdChnbG0zLCBYX3Rlc3QsIHR5cGU9InJlc3BvbnNlIikpCnJlc3VsdHNbImdsbS1yaWRnZSIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJnbG0tcmlkZ2UiLF0KYGBgCgojIyMgUmFuZG9tIEZvcmVzdAoKVG8gaW1wcm92ZSBwZXJmb3JtYW5jZSwgd2UgZHJhdyBvbiB0aGUgdXNhZ2Ugb2Ygbm9uLWxpbmVhciB0cmVlLWJhc2VkIG1vZGVscywgc3BlY2lmaWNhbGx5IHJhbmRvbSBmb3Jlc3RzLiBJbnR1aXRpdmVseSwgYSByYW5kb20gZm9yZXN0IGF2ZXJhZ2VzIGRpZmZlcmVudCBkZWNpc2lvbiB0cmVlcyAoa25vd24gYXMgYmFnZ2luZykgc28gYXMgdG8gcmVkdWNlIHRoZSB2YXJpYW5jZSBvZiBpbmRpdmlkdWFsIHRyZWVzLgoKYGBge3IgcmYgLG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0KcmZfcmVjaXBlIDwtIHJlY2lwZSh0YXJnZXR+LiwgZGF0YSA9IGRmX3RyYWluKQoKcmZfbW9kZWwgPC0gCiAgcmFuZF9mb3Jlc3QodHJlZXM9MTAwKSAlPiUKICBzZXRfZW5naW5lKCJyYW5nZXIiLCBpbXBvcnRhbmNlPSJpbXB1cml0eSIsIHNlZWQ9MjAyMSkgJT4lCiAgc2V0X21vZGUoImNsYXNzaWZpY2F0aW9uIikKCnJmX3dvcmtmbG93IDwtIHdvcmtmbG93KCkgJT4lCiAgYWRkX3JlY2lwZShyZl9yZWNpcGUpICU+JQogIGFkZF9tb2RlbChyZl9tb2RlbCkKCnJmMSA8LSBmaXQocmZfd29ya2Zsb3csIGRmX3RyYWluKQpyYW5nZXJfb2JqIDwtIHB1bGxfd29ya2Zsb3dfZml0KHJmMSkkZml0CiMgcGxvdCBmZWF0dXJlIGltcG9ydGFuY2VzCnJmX2ZlYXRfaW1wIDwtIHJvd25hbWVzX3RvX2NvbHVtbihkYXRhLmZyYW1lKHJhbmdlcl9vYmokdmFyaWFibGUuaW1wb3J0YW5jZSkpOwpuYW1lcyhyZl9mZWF0X2ltcCkgPC0gYygiZmVhdCIsICJpbXBvcnRhbmNlIikKZ2dwbG90KHJmX2ZlYXRfaW1wLCBhZXMoeCA9IHJlb3JkZXIoZmVhdCwgaW1wb3J0YW5jZSksIHkgPSBpbXBvcnRhbmNlKSkrIAogICAgICBnZW9tX2JhcihzdGF0PSJpZGVudGl0eSIsIHBvc2l0aW9uPSJkb2RnZSIpKyBjb29yZF9mbGlwKCkrCiAgICAgIHlsYWIoIkZlYXR1cmUgSW1wb3J0YW5jZSAoR2luaSBJbXB1cml0eSkiKSsKICAgICAgeGxhYigiRmVhdHVyZSIpKwogICAgICBnZ3RpdGxlKCJSYW5kb20gRm9yZXN0IEZlYXR1cmUgSW1wb3J0YW5jZXMiKQojZXZhbHVhdGUgbWV0cmljcwpwcmVkX3RyYWluIDwtIHVubGlzdChwcmVkaWN0KHJmMSxkZl90cmFpbix0eXBlPSdwcm9iJylbLDJdKQpwcmVkX3Rlc3QgPC0gdW5saXN0KHByZWRpY3QocmYxLCBkZl90ZXN0LCB0eXBlPSdwcm9iJylbLDJdKQpyZXN1bHRzWyJyZiIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJyZiIsXQpgYGAKCmBgYHtyIHBkcCwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KdGVtcCA8LSBmdW5jdGlvbih4KXtwYXJ0aWFsKHJhbmdlcl9vYmosIHRyYWluPWRmX3RyYWluLCBwcmVkLnZhciA9IHgsIHBsb3QgPSBUUlVFLCBwbG90LmVuZ2luZSA9ICJnZ3Bsb3QyIiwgcGFyb3B0cyA9IGxpc3QoLnBhY2thZ2VzID0gInJhbmdlciIpKX0KcGxvdHMgPC0gbGFwcGx5KG5hbWVzKGRmX3RyYWluKVtjb250X2ZlYXRzXSwgdGVtcCkKd3JhcF9wbG90cyhwbG90cykKYGBgCgpUaGUgcmFuZG9tIGZvcmVzdCBoYXMgYSB0ZXN0IGFjY3VyYWN5IG9mIDAuODM2IGFuZCBhIHRlc3QgQVVDIG9mIDAuODcyLCB3aGljaCBpcyBoaWdoZXIgdGhhbiB0aGUgcHJldmlvdXMgbGluZWFyIG1vZGVscy4gSG93ZXZlciwgdGhlIHRyYWluIGFjY3VyYWN5IGFuZCBBVUMgYXJlIHNpZ25pZmljYW50bHkgaGlnaGVyIHRoYW4gdGhlIHRlc3QgcGVyZm9ybWFuY2UsIHdoaWNoIHN1Z2dlc3QgdGhhdCB0aGVyZSBtYXkgYmUgc29tZSBkZWdyZWUgb2Ygb3ZlcmZpdHRpbmcgdG8gdGhlIHRyYWluIGRhdGEuIAoKUmFuZG9tIGZvcmVzdHMgY2FuIGJlIHVzZWQgdG8gcmFuayB0aGUgaW1wb3J0YW5jZSBvZiBkaWZmZXJlbnQgZmVhdHVyZXMuIFNwZWNpZmljYWxseSwgdGhlIHgtYXhpcyBpcyB0aGUgTWVhbiBEZWNyZWFzZSBBY2N1cmFjeSwgd2hpY2ggcmVwb3J0cyBob3cgbXVjaCBhY2N1cmFjeSB0aGUgbW9kZWwgbG9zZXMgd2hlbiB3ZSBleGNsdWRlIHRoaXMgdmFyaWFibGUuIFRoZSBtb3JlIHRoZSBhY2N1cmFjeSBmYWxscyBieSwgdGhlIG1vcmUgaW1wb3J0YW50IHRoZSBwYXJ0aWN1bGFyIHZhcmlhYmxlIGlzLiBOb3RlIGhlcmUgdGhhdCBmb3IgY2F0ZWdvcmljYWwgdmFyaWFibGVzLCBlYWNoIGxldmVsIG9mIHRoZSBjYXRlZ29yeSBpcyBjbGFzc2lmaWVkIGFzIGEgc2luZ2xlIHZhcmlhYmxlLiBJbiB0aGlzIHBsb3QsIHdlIHJlY29yZGVkIHRoZSAzMCBtb3N0IGltcG9ydGFudCB2YXJpYWJsZXMuIAoKV2UgdGhlbiBydW4gYW5vdGhlciByYW5kb20gZm9yZXN0IHdpdGggdGhlIG1vc3QgaW1wb3J0YW50IGZlYXR1cmVzLiBJbiBkb2luZyBzbywgd2UgaG9wZSB0byByZWR1Y2UgdGhlIGRlZ3JlZSBvZiBvdmVyZml0dGluZyBieSByZWR1Y2luZyB0aGUgY29tcGxleGl0eSBvZiB0aGUgbW9kZWwuIEhvd2V2ZXIsIGl0IGRvZXMgbm90IG1ha2Ugc2Vuc2UgdG8gZHJvcCBzb21lIGxldmVscyBvZiBhIGNhdGVnb3JpY2FsIHZhcmlhYmxlIHdoaWxlIGluY2x1ZGluZyB0aGUgb3RoZXIgbGV2ZWxzLiBIZW5jZSwgYXMgbG9uZyBhcyBhIGxldmVsIGlzIHByZXNlbnQgaW4gdGhlIHRvcCAzMCBmZWF0dXJlcywgd2Ugd2lsbCBpbmNsdWRlIHRoZSBlbnRpcmUgY2F0ZWdvcnkgaW4gb3VyIHVwZGF0ZWQgcmFuZG9tIGZvcmVzdCBtb2RlbC4gVGhpcyByZXN1bHRzIGluIHVzIGtlZXBpbmcgb25seSAyMiB2YXJpYWJsZXMsIGZyb20gYW4gaW5pdGlhbCAzMC4gCgpPdXIgcmVkdWNlZCByYW5kb20gZm9yZXN0IGhhcyBhIHNsaWdodGx5IGltcHJvdmVkIHRlc3QgYWNjdXJhY3kgYW5kIGEgc2xpZ2h0bHkgZGVjcmVhc2VkIHRlc3QgQVVDLiBIb3dldmVyLCBpdCBkb2VzIG5vdCBzb2x2ZSB0aGUgcG90ZW50aWFsIHByb2JsZW0gb2Ygb3ZlcmZpdHRpbmcgYXMgdHJhaW4gcGVyZm9ybWFuY2UgaXMgc3RpbGwgc2lnbmlmaWNhbnRseSBiZXR0ZXIgdGhhbiB0ZXN0IHBlcmZvcm1hbmNlLiBJbiBmYWN0LCB0cmFpbiBwZXJmb3JtYW5jZSBvbiB0aGUgcmVkdWNlZCByYW5kb20gZm9yZXN0IGlzIGJldHRlciB0aGFuIHRoZSByYW5kb20gZm9yZXN0IHdpdGggYSBmdWxsIHNldCBvZiB2YXJpYWJsZXMgLSB0aGUgcmVkdWNlZCBjb21wbGV4aXR5IG9mIHRoZSBtb2RlbCBlbmFibGVkIGl0IHRvIGhhdmUgYSBsb3dlciBiaWFzIG9uIHRoZSB0cmFpbmluZyBzZXQuIAoKCiMjIyBYR0Jvb3N0CgpGb3IgY29tcGxldGVuZXNzLCB3ZSBhbHNvIGNvbnNpZGVyIHRoZSBgeGdib29zdGAgbGlicmFyeSBmb3IgKipncmFkaWVudCBib29zdGVkIGRlY2lzaW9uIHRyZWVzKiouIEdyYWRpZW50IEJvb3N0ZWQgRGVjaXNpb24gVHJlZXMuIFRoZSBYR0Jvb3N0IHBhY2thZ2UsIGludHJvZHVjZWQgaW4gW0BjaGVuMjAxNnhnYm9vc3RdIGlzIGEgdmFyaWFudCBvZiBHcmFkaWVudCBCb29zdGVkIERlY2lzaW9uIFRyZWVzIFtAaGFzdGllMjAwOWVsZW1lbnRzLCBwcC4gMzUzLTM3NF0uIEZvciBHcmFkaWVudCBCb29zdGluZyBUcmVlcywgZWFjaCBkZWNpc2lvbiB0cmVlIGlzIHRyYWluZWQgc2VxdWVudGlhbGx5IG9uIHRoZSAqcmVzaWR1YWxzKiBvZiB0aGUgcHJldmlvdXMgZGVjaXNpb24gdHJlZSwgd2hpY2ggaGFzIHRoZSBlZmZlY3Qgb2YgcmVkdWNpbmcgYmlhcy4KCmBgYHtyIHhnYiwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KZG15X3RyYWluIDwtIGR1bW15VmFycygifi4iLCBkYXRhID0gZGZfdHJhaW5bLC1sZW5ndGgoZGZfdHJhaW4pXSkKZG15X3Rlc3QgPC0gZHVtbXlWYXJzKCJ+LiIsIGRhdGEgPSBkZl90ZXN0WywtbGVuZ3RoKGRmX3Rlc3QpXSkKWF90cmFpbiA8LSBhcy5tYXRyaXgoZGF0YS5mcmFtZShwcmVkaWN0KGRteV90cmFpbixkZl90cmFpbikpKQpYX3Rlc3QgPC0gYXMubWF0cml4KGRhdGEuZnJhbWUocHJlZGljdChkbXlfdGVzdCxkZl90ZXN0KSkpCnlfdHJhaW4gPSBhcy5pbnRlZ2VyKGFzLm1hdHJpeChkZl90cmFpbiR0YXJnZXQpKQp5X3Rlc3QgPSBhcy5pbnRlZ2VyKGFzLm1hdHJpeChkZl90ZXN0JHRhcmdldCkpCmJzdCA8LSB4Z2Jvb3N0KGRhdGEgPSBYX3RyYWluLCBsYWJlbD15X3RyYWluLCBtYXhfZGVwdGggPSAyLCBucm91bmQgPSAxMCwgCiAgICAgICAgICAgICAgIHZlcmJvc2U9MCwKICAgICAgICAgICAgICAgb2JqZWN0aXZlPSdiaW5hcnk6bG9naXN0aWMnLAogICAgICAgICAgICAgICBldmFsX21ldHJpYz0ibG9nbG9zcyIpCgpwcmVkX3RyYWluIDwtIHByZWRpY3QoYnN0LCBYX3RyYWluLCB0eXBlPSJyZXNwb25zZSIpCnByZWRfdGVzdCA8LSBwcmVkaWN0KGJzdCwgWF90ZXN0LCB0eXBlPSJyZXNwb25zZSIpCnJlc3VsdHNbInhnYiIsXSA8LSBkaWFnbm9zaXMocHJlZF90cmFpbiwgcHJlZF90ZXN0LCBkZl90cmFpbiR0YXJnZXQsIGRmX3Rlc3QkdGFyZ2V0KQpyZXN1bHRzWyJ4Z2IiLF0KCmltcG9ydGFuY2VfbWF0cml4IDwtIHhnYi5pbXBvcnRhbmNlKG1vZGVsPWJzdCkKeGdiLnBsb3QuaW1wb3J0YW5jZShpbXBvcnRhbmNlX21hdHJpeCkKIyBzaGFwbGV5IHZhbHVlcyAgCnhnYm9vc3Q6OnhnYi5nZ3Bsb3Quc2hhcC5zdW1tYXJ5KFhfdGVzdCwgbW9kZWwgPSBic3QsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0YXJnZXRfY2xhc3MgPSAxLCB0b3BfbiA9IDIwKSAgIyBTdW1tYXJ5IHBsb3QKYGBgCgojIyMgQ2F0Qm9vc3QKCldlIGFsc28gY29uc2lkZXIgYnJpZWZseSBleGFtaW5lIHRoZSBgY2F0Ym9vc3RgIGxpYnJhcnkgZm9yICoqZ3JhZGllbnQgYm9vc3RlZCBkZWNpc2lvbiB0cmVlcyoqLCBnaXZlbiBpdHMgcG9wdWxhcml0eSBvbiBtYWNoaW5lIGxlYXJuaW5nIGNvbXBldGl0aW9ucyBzdWNoIGFzIEthZ2dsZS4gVGhlIENhdEJvb3N0IGxpYnJhcnkgaGFzIHRoZSBhZHZhbnRhZ2Ugb2YgbGVhcm5pbmcgYSAqdGFyZ2V0IGVuY29kaW5nKiwgaS5lLiBzb21lIG51bWVyaWNhbCB2YWx1ZSBmb3IgZXZlcnkgY2F0ZWdvcnkgZm9yIGVhY2ggIGNhdGVnb3JpY2FsIHZhcmlhYmxlcy4gRnJvbSBhbiBpbXBsZW1lbnRhdGlvbiBwb2ludCBvZiB2aWV3LCB0aGlzIG1heSByZWR1Y2UgdGhlIHByZXByb2Nlc3NpbmcgdGhhdCBtYXkgYmUgcmVxdWlyZWQuRm9yIGRldGFpbHMgb24gQ2F0Qm9vc3QsIHJlZmVyIHRvIFtAcHJva2hvcmVua292YTIwMTdjYXRib29zdF0uCgpgYGB7ciBjYiwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KWF90cmFpbiA9IGRmX3RyYWluWyxjKGNhdF9mZWF0cywgY29udF9mZWF0cyldCnlfdHJhaW4gPSBhcy5pbnRlZ2VyKGRmX3RyYWluJHRhcmdldCkKWF90ZXN0ID0gZGZfdGVzdFssYyhjYXRfZmVhdHMsIGNvbnRfZmVhdHMpXQp5X3Rlc3QgPSBhcy5pbnRlZ2VyKGRmX3Rlc3QkdGFyZ2V0KQoKcG9vbCA8LSBjYXRib29zdC5sb2FkX3Bvb2woWF90cmFpbiwgeV90cmFpbiwgY2F0X2ZlYXR1cmVzID0gY2F0X2ZlYXRzKQptb2RlbCA8LSBjYXRib29zdC50cmFpbihwb29sLCBwYXJhbXM9bGlzdChkZXB0aCA9IDgsIGl0ZXJhdGlvbnMgPSAxMCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxvc3NfZnVuY3Rpb249J0xvZ2xvc3MnLCB2ZXJib3NlPTApKQoKcHJlZF90cmFpbiA8LSBjYXRib29zdC5wcmVkaWN0KG1vZGVsLCBjYXRib29zdC5sb2FkX3Bvb2woWF90cmFpbiksIHByZWRpY3Rpb25fdHlwZSA9ICdQcm9iYWJpbGl0eScpCnByZWRfdGVzdCA8LSBjYXRib29zdC5wcmVkaWN0KG1vZGVsLCBjYXRib29zdC5sb2FkX3Bvb2woWF90ZXN0KSwgcHJlZGljdGlvbl90eXBlID0gJ1Byb2JhYmlsaXR5JykKCiMgZmVhdHVyZSBpbXBvcnRhbmNlCmZlYXRfaW1wb3J0YW5jZSA8LSBjYXRib29zdC5nZXRfZmVhdHVyZV9pbXBvcnRhbmNlKG1vZGVsLCBwb29sKQppbXBvcnRhbmNlcyA8LSBkYXRhLmZyYW1lKGZlYXRfaW1wb3J0YW5jZVtvcmRlcihmZWF0X2ltcG9ydGFuY2UsIGRlY3JlYXNpbmc9RkFMU0UpLF0pCmltcG9ydGFuY2VzJGZlYXR1cmVzID0gcm93bmFtZXMoaW1wb3J0YW5jZXMpCm5hbWVzKGltcG9ydGFuY2VzKSA8LSBjKCJpbXBvcnRhbmNlIiwiZmVhdHVyZXMiKQppbXBvcnRhbmNlcyRmZWF0dXJlcyA8LSBmYWN0b3IoaW1wb3J0YW5jZXMkZmVhdHVyZXMsIGxldmVsPWltcG9ydGFuY2VzJGZlYXR1cmVzKQpnZ3Bsb3QoaW1wb3J0YW5jZXMsIGFlcyh4PWltcG9ydGFuY2UsIHk9ZmVhdHVyZXMpKSArIAogIGdlb21fYmFyKHN0YXQ9ImlkZW50aXR5IikgKwogIGdndGl0bGUoIkNhdEJvb3N0IEZlYXR1cmUgSW1wb3J0YW5jZSIpCgojU2hhcGxleSBWYWx1ZXMKZGF0YV9zaGFwX3RyZWUgPC0gY2F0Ym9vc3QuZ2V0X2ZlYXR1cmVfaW1wb3J0YW5jZShtb2RlbCwgcG9vbCA9IHBvb2wsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdHlwZSA9ICJTaGFwVmFsdWVzIikKZGF0YV9zaGFwX3RyZWUgPC0gZGF0YS5mcmFtZShkYXRhX3NoYXBfdHJlZVssIC1uY29sKGRhdGFfc2hhcF90cmVlKV0pIApuYW1lcyhkYXRhX3NoYXBfdHJlZSkgPSBuYW1lcyhkZlssIGMoY2F0X2ZlYXRzLCBjb250X2ZlYXRzKV0pCgojIGdncGxvdChzdGFjayhkYXRhX3NoYXBfdHJlZSksIGFlcyh4ID0gaW5kLCB5ID0gdmFsdWVzKSkgKwojICAgICBnZW9tX3BvaW50KGFlcyhjb2xvciA9IHZhbHVlcykpICsgY29vcmRfZmxpcCgpICsgCiMgICAgIGdndGl0bGUoIlNoYXBsZXkgVmFsdWVzIGJ5IHZhcmlhYmxlIikgICsgc2NhbGVfY29sb3JfdmlyaWRpc19jKCkKCnJlc3VsdHNbImNhdGJvb3N0IixdIDwtIGRpYWdub3NpcyhwcmVkX3RyYWluLCBwcmVkX3Rlc3QsIGRmX3RyYWluJHRhcmdldCwgZGZfdGVzdCR0YXJnZXQpCnJlc3VsdHNbImNhdGJvb3N0IixdCmBgYAoKIyMgUmVzdWx0cyBhbmQgRXZhbHVhdGlvbgoKYGBge3IgcmVzdWx0cywgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KcmVzdWx0c1tvcmRlcihyZXN1bHRzJHRlc3RfYXVjLCByZXN1bHRzJHRlc3RfYWNjKSxdCmBgYAoKQWx0aG91Z2ggdGhlIHRyZWUtYmFzZWQgbWV0aG9kcyBhcmUgbGVzcyBpbnRlcnByZXRhYmxlIGFuZCBtb3JlICJibGFjayBib3giIHRvIHNvbWUgZXh0ZW50LCB3ZSBjYW4gbWFrZSB1c2Ugb2YgbW9kZWwgaW50ZXJwcmV0YWJpbGl0eSB0ZWNobmlxdWVzLgoKSXQgY291bGQgYmUgdGhhdCBvdXIgcmVzdXRscyBhcmUgbm90IGZ1bGx5IHJvYnVzdCwgZ2l2ZW4gd2UgaGF2ZSBzdWJzYW1wbGVkIHRoZSBvcmlnaW5hbCBkYXRhLgoKIyMgQ29uY2x1c2lvbgoKSW4gdGhpcyBwcm9qZWN0LCB3ZSBkZW1vbnN0cmF0ZWQgdGhlIHVzZSBvZiBsb2dpc3RpYyByZWdyZXNzaW9uLCBncmFkaWVudCBkZXNjZW50LCByZWd1bGFyaXNhdGlvbiwgcmFuZG9tIGZvcmVzdCwgZ3JhZGllbnQgYm9vc3RpbmcgYW5kIGh5cGVycGFyYW1ldGVyIHR1bmluZyB0ZWNobmlxdWVzIHRvIGFjaGlldmUgaW50ZXJwcmV0YWJpbGl0eSBhbmQgbW9kZWwgYWNjdXJhY3kgKGluIHNlcGFyYXRlIGNhc2VzKSBpbiBwcmVkaWN0aW5nIHRoZSBhbW91bnQgb2YgYW4gaW5zdXJhbmNlIGNsYWltLiBNb2RlbCBfX18gd2FzIHRoZSBtb2RlbCB3aXRoIGhpZ2hlc3QgQVVDLCBhbHRob3VnaCBpbnRlcnByZXRhYmlsaXR5IHdhcyBzYWNyaWZpY2VkLiBPbiB0aGUgb3RoZXIgaGFuZCwgb3VyIGJhc2VsaW5lIG1vZGVsIHdpdGggb25seSBhIGZldyBwcmVkaWN0b3JzIGlzIGVhc3kgdG8gaW50ZXJwcmV0LCBob3dldmVyIGl0IGhhcyBhIHJlbGF0aXZlbHkgbG93IEFVQyBvZiAwLjcwMy4gSW4gcHJhY3RpY2UsIGRlcGVuZGluZyBvbiB3aGV0aGVyIHRoZSBnb2FscyBvZiB0aGUgY29tcGFueSBsZWFuIHRvd2FyZHMgcHJlZGljdGlvbiBvciBleHBsYW5hdGlvbiwgYW4gYXBwcm9wcmlhdGUgdHJhZGUtb2ZmIGJldHdlZW4gbW9kZWwgY29tcGxleGl0eSBhbmQgaW50ZXJwcmV0YWJpbGl0eSBoYXMgdG8gYmUgY2hvc2VuLiAKCkZyb20gdGhlIGluc3VyZXLigJlzIHByb2ZpdCBwZXJzcGVjdGl2ZSwgdW5kZXJzdGFuZGluZyB3aGljaCBjaGFyYWN0ZXJpc3RpY3MgYXJlIGhpZ2hseSBjb3JyZWxhdGVkIHdpdGggbGFyZ2UgYW1vdW50cyBvZiBjbGFpbXMgY291bGQgYWxzbyBiZSB1c2VkIHRvIGluZm9ybSB3aGV0aGVyIG9yIG5vdCBhIHBhcnRpY3VsYXIgaW5zdXJhbmNlIGFwcGxpY2F0aW9uIGlzIGFjY2VwdGVkLCBldmVuIGlmIGNhdXNhbGl0eSBjYW5ub3QgYmUgaW5mZXJyZWQuIEhvd2V2ZXIsIHRoaXMgbWlnaHQgbGVhZCB0byBzb21lIGxlZ2FsIGFuZC9vciBldGhpY2FsIGlzc3Vlcy4gRm9yIGV4YW1wbGUsIHRoZSBVS+KAmXMgMjAxMCBFcXVhbGl0eSBBY3QgbWFrZXMgZGlzY3JpbWluYXRpbmcgb24gbmluZSBwcm90ZWN0ZWQgY2hhcmFjdGVyaXN0aWNzLCBpbmNsdWRpbmcgYWdlLCBnZW5kZXIsIHJhY2UgYW5kIHJlbGlnaW9uLCBpbGxlZ2FsIChQYXR0bmksIDIwMjApLiBUaGVyZWZvcmUsIHByb3BlciBkYXRhIGdvdmVybmFuY2UgbmVlZHMgdG8gYmUgbWFpbnRhaW5lZCBhbmQgcHJpdmFjeSBpbXBhY3QgYXNzZXNzbWVudHMgbmVlZCB0byBiZSBjb25kdWN0ZWQgYmVmb3JlIGFueSBtYWNoaW5lIGxlYXJuaW5nIG1vZGVscyBvZiB0aGlzIGtpbmQgYXJlIGRlcGxveWVkIGluIGluZHVzdHJ5IChHRFBSLCAyMDE4KS4KCgojIyBCaWJsaW9ncmFwaHkKCjo6OiB7I3JlZnN9Cjo6OgoKIyMgQXBwZW5kaXgKCmBgYHtyfQpzZXQuc2VlZCgyMDIxKQpjdl9zcGxpdHMgPC0gcnNhbXBsZTo6dmZvbGRfY3YoZGZfdHJhaW4sIHN0cmF0YSA9IHRhcmdldCwgdj0gMykKbW9kIDwtIGxvZ2lzdGljX3JlZyhwZW5hbHR5ID0gdHVuZSgpLAogICAgICAgICAgICAgICAgICAgIG1peHR1cmUgPSB0dW5lKCkpICU+JQogIHNldF9lbmdpbmUoImdsbW5ldCIpCgpnbG1uZXRfcmVjaXBlIDwtIHJlY2lwZSh0YXJnZXR+LixkYXRhID0gZGZfdHJhaW4pICU+JSAKICBzdGVwX2R1bW15KGFsbF9ub21pbmFsKCksIC1hbGxfb3V0Y29tZXMoKSkKCmdsbW5ldF93b3JrZmxvdzwtIHdvcmtmbG93KCkgJT4lCiAgYWRkX3JlY2lwZShnbG1uZXRfcmVjaXBlKSAlPiUKICBhZGRfbW9kZWwobW9kKQoKZ2xtbl9zZXQgPC0gcGFyYW1ldGVycyhwZW5hbHR5KHJhbmdlID0gYygtNSwxKSwgdHJhbnMgPSBsb2cxMF90cmFucygpKSwKICAgICAgICAgICAgICAgICAgICAgICBtaXh0dXJlKCkpCgpnbG1uX2dyaWQgPC0gCiAgZ3JpZF9yZWd1bGFyKGdsbW5fc2V0LCBsZXZlbHMgPSBjKDcsIDUpKQpjdHJsIDwtIGNvbnRyb2xfZ3JpZChzYXZlX3ByZWQgPSBUUlVFLCB2ZXJib3NlID0gVFJVRSkKCmdsbW5fdHVuZSA8LSAKICB0dW5lX2dyaWQoZ2xtbmV0X3dvcmtmbG93LAogICAgICAgICAgICByZXNhbXBsZXMgPSBjdl9zcGxpdHMsCiAgICAgICAgICAgIGdyaWQgPSBnbG1uX2dyaWQsCiAgICAgICAgICAgIG1ldHJpY3MgPSBtZXRyaWNfc2V0KHJvY19hdWMpLAogICAgICAgICAgICBjb250cm9sID0gY3RybCkKCgpiZXN0X2dsbW4gPC0gc2VsZWN0X2Jlc3QoZ2xtbl90dW5lLCBtZXRyaWMgPSAicm9jX2F1YyIpCgpnbG1uZXRfbW9kZWwgPC0gCiAgbG9naXN0aWNfcmVnKCkgJT4lCiAgc2V0X2VuZ2luZSgiZ2xtbmV0Iiwgc2VlZD0yMDIxKSAlPiUKICBzZXRfbW9kZSgiY2xhc3NpZmljYXRpb24iKQoKCgpnbG0zIDwtIGZpdChnbG1uZXRfd29ya2Zsb3csIGRhdGEgPSBkZl90cmFpbikKYGBgCgoKYGBge3J9CnhnYl9zcGVjIDwtIGJvb3N0X3RyZWUoCiAgdHJlZXMgPSAxMDAsIAogIHRyZWVfZGVwdGggPSB0dW5lKCksCiAgbGVhcm5fcmF0ZSA9IHR1bmUoKSAgICAgICAgICAgICAgICAgICAgICAgICAjIyBzdGVwIHNpemUKKSAlPiUgCiAgc2V0X2VuZ2luZSgieGdib29zdCIpICU+JSAKICBzZXRfbW9kZSgiY2xhc3NpZmljYXRpb24iKQoKeGdiX2dyaWQgPC0gZ3JpZF9sYXRpbl9oeXBlcmN1YmUoCiAgdHJlZV9kZXB0aCgpLAogIGxlYXJuX3JhdGUoKSwKICBzaXplID0gNQopCgp4Z2Jfd2YgPC0gd29ya2Zsb3coKSAlPiUKICBhZGRfZm9ybXVsYSh0YXJnZXQgfiAuKSAlPiUKICBhZGRfbW9kZWwoeGdiX3NwZWMpCgpzZXQuc2VlZCgxMjMpCnZiX2ZvbGRzIDwtIHZmb2xkX2N2KGRmX3RyYWluLCBzdHJhdGEgPSB0YXJnZXQpCgpkb1BhcmFsbGVsOjpyZWdpc3RlckRvUGFyYWxsZWwoKQoKc2V0LnNlZWQoMjM0KQp4Z2JfcmVzIDwtIHR1bmVfZ3JpZCgKICB4Z2Jfd2YsCiAgcmVzYW1wbGVzID0gdmJfZm9sZHMsCiAgZ3JpZCA9IHhnYl9ncmlkLAogIGNvbnRyb2wgPSBjb250cm9sX2dyaWQoc2F2ZV9wcmVkID0gVFJVRSkKKQpiZXN0X2F1YyA8LSBzZWxlY3RfYmVzdCh4Z2JfcmVzLCAicm9jX2F1YyIpCmZpbmFsX3hnYiA8LSBmaW5hbGl6ZV93b3JrZmxvdygKICB4Z2Jfd2YsCiAgYmVzdF9hdWMKKQpsaWJyYXJ5KHZpcCkKCmZpbmFsX3hnYiAlPiUKICBmaXQoZGF0YSA9IHZiX3RyYWluKSAlPiUKICBwdWxsX3dvcmtmbG93X2ZpdCgpICU+JQogIHZpcChnZW9tID0gInBvaW50IikKCmZpbmFsX3JlcyA8LSBsYXN0X2ZpdChmaW5hbF94Z2IsIGRmX3NwbGl0KQoKY29sbGVjdF9tZXRyaWNzKGZpbmFsX3JlcykKYGBgCgpgYGB7cn0KeGdiX3JlcyAlPiUKICBjb2xsZWN0X21ldHJpY3MoKSAlPiUKICBmaWx0ZXIoLm1ldHJpYyA9PSAicm9jX2F1YyIpICU+JQogIHNlbGVjdChtZWFuLCBtdHJ5OnNhbXBsZV9zaXplKSAlPiUKICBwaXZvdF9sb25nZXIobXRyeTpzYW1wbGVfc2l6ZSwKICAgICAgICAgICAgICAgdmFsdWVzX3RvID0gInZhbHVlIiwKICAgICAgICAgICAgICAgbmFtZXNfdG8gPSAicGFyYW1ldGVyIgogICkgJT4lCiAgZ2dwbG90KGFlcyh2YWx1ZSwgbWVhbiwgY29sb3IgPSBwYXJhbWV0ZXIpKSArCiAgZ2VvbV9wb2ludChhbHBoYSA9IDAuOCwgc2hvdy5sZWdlbmQgPSBGQUxTRSkgKwogIGZhY2V0X3dyYXAofnBhcmFtZXRlciwgc2NhbGVzID0gImZyZWVfeCIpICsKICBsYWJzKHggPSBOVUxMLCB5ID0gIkFVQyIpCmBgYAoKYGBge3J9CiJodHRwczovL2N1cnNvLXIuZ2l0aHViLmlvL3RyZWVzbmlwL2luZGV4Lmh0bWwiCmxpYnJhcnkodHJlZXNuaXApCmBgYAo=